黑马程序员技术交流社区

标题: 集合 [打印本页]

---

作者: 丨灬勿忘初心灬    时间: 2019-4-18 18:12
标题: 集合
1.数组
        1.1 特点：底层连续,有索引,增删慢，查询快，长度不可变
       
       
2.链表
        2.1 特点：无索引,增删快,查询慢
        2.2 链表的分类：
                        1.单链表
                        2.双向链表
                                 比单向链表有遍历优势，可以判断要查找的元素靠近头还是靠近尾
                        3.循环链表
                        4.链表有大量对头尾的操作
                       
                       
3.HashSet 不能存储重复元素理论                        (n - 1) & hash   就是计算索引的方法
        1.当存储元素时，会首先调用其hashCode 方法，会根据hashCode 方法去判断到底应该存储在
        数组上的哪个位置上，如果这个位置上没有元素，那么直接存储
                 如果有元素，则进行eqauls 方法比较
                                                   eqauls 比较结果 相同，如果相同， 不存
                                                                                                 如果不同，则挂在数组上
        2.LinkedHashSet 有序的Set集合(去重,保证顺序  了解)
         

3.1集合的体系结构
        单列集合
        在jdk1.5 以前 Collection 父类
          jdk1.5 以后 迭代器接口
       
        两大体系
        第一大体系
        List(有序,可重复)
        ArryaList ： 底层是一个数组->  查询快,有索引，底层连续(?)，增删慢 ，长度固定
        LinkedList(不强制要求大家记住他的api)： 底层是一个双向链表 ->  双向链表 遍历效率可能高于单向链表 可以判断你要查找的元素是靠近头，还是靠近尾
            add
                addFirst
                addLast
                removeFirst
                removeLast
                 
       
        第二大体系
        Set(无序,不可重复)
        HashSet(重要 ： HashSet 不能重复的原因)
                 1.首先计算要存储元素的hashCode 值，通过hashCode 值和 数组长度 一起计算出来对应的
                 数组索引，如果数组索引上没有元素-->直接存储
                                  
                 2.如果有调用eqauls 方法
                                2.1 相等 ：不存
                                2.2 不相等：存
                               
        LinkedHashSet
        TreeSet
       
       


                                                                                                 
4.TreeSet 原理  (左中右原则)
        TreeSet ： 可以排序 ，不可重复
        ts.add(对象)
                  有两种可以告诉treeSet 排序的规则的方式
                    1.比较器排序
                    2.自然排序        调用无参构造方法
                       
                       
5. hashCode 方法  32 位 二进制数，其中二进制的最高位是表示正负而不是表示值的
                最高位是1  ,就是一个负数  最高位如果是个0 ，就是一个正数 (常识)
               

        以int 方式来返回的对应的值(在Object类中是通过内存地址值计算出来)
                                                           在String类中是通过内容计算
       

       




       
6.面试重点(目前阶段很难)
        hash冲突 指的是不同的hashCode 值所对应的元素索引在数组中一样
        hash冲突算法： 就是为了解决hash冲突
       
        HashSet
        public HashSet() {
        map = new HashMap<>();
    }
        // HashSet 实际上在借HashMap
        public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
       
        HashMap
       
        public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
        //在存储元素时,首先调用了存储元素的的 hash方法
       
        static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }


        option1 : (h = key.hashCode()) ^ (h >>> 16);
       
        N * name  + H* age       -->hashCode
                 10      20               --> 30
                 20      10              --> 30
                 15      15              --> 30
                 
                        01111111 &  1      &  同1得 1   不同得0  
                          确保 n 是一个偶数  n- 1  就一定是一个奇数
        option2 : (n - 1) & hash  (尽可能多的位数参与到运算)
                101010101010
                          000000  &       同1得 1   不同得0  
                ------------------
        ----》                   0
                                  末尾數 ：  有可能是0 ，儅hashCode 为0 时，得出的结果是 0
                                                        ，有可能是1 ，儅hashCode 为1 时，得出来结果是1
                                       
                          
       

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2