Java集合_HashMap篇

摘要：如果不重复，判断是否是类型，如果是红黑树，直接插入。条件为时执行链表转红黑树，然后插入。为了避免尾部遍历。添加元素时，如果超过阈值，就要进行扩容，如果两个元素同时添加，线程和线程可能同时扩容。

    HashMap是存键值对(key-value)映射的数据结构，由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。通过下图可以对HashMap有一个直观的认识。

put操作（JDK1.8版）

    1）计算key的hash值（计算过程下面会详细介绍）。

    2）如果数组table是否为null或长度是否等于0，条件为true时进行数据table扩容（实际执行resize方法）。

    3）根据hash值计算Value将要存放的位置，即计算数组table索引（计算过程下面会详细讲）。

    4）判断table[i]是否是null，如果是null直接进行Value插入。

    5）如果table[i]不是null，接着判断key是否重复，如果重复直接进行覆盖插入。

    6）如果key不重复，判断table[i]是否是TreeNode类型，如果是红黑树，直接插入。

    7）如果不是TreeNode就遍历链表，遍历时预判断插入新的Value后，链表长度是否大于等于8。条件为True时执行链表转红黑树，然后插入Value。

    8）如果上面链表长度小于8执行链表插入。

    9）最后检查数组是否需要扩容。

详细代码：

    public V put(K key, V value) {
        //调用putVal方法
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node[] tab;  //缓存底层数组用,都是指向一个地址的引用
        Node p;      //插入数组的桶i处的键值对节点
        int n;            //底层数组的长度
        int i;            //插入数组的桶的下标
        //刚开始table是null或空的时候，初始化个默认的table；为tab和n赋值，tab指向底层数组，n为底层数组的长度
        if ((tab = table) == null || (n = tab.length) == 0){
            n = (tab = resize()).length;
        }
        //(n - 1) & hash：根据hash值算出插入点在底层数组的桶的位置，即下标值；为p赋值，也为i赋值（不管碰撞与否，都已经赋值了）
        //如果在数组上，没有发生碰撞，即当前要插入的位置上之前没有插入过值，则直接在此位置插入要插入的键值对
        if ((p = tab[i = (n - 1) & hash]) == null){
            tab[i] = newNode(hash, key, value, null);//插入的节点的next属性是null
        } else {    //发生碰撞，即当前位置已经插入了值
            Node e;    //中间变量吧，跟冒泡排序里面的那个中间变量似的，起到个值交换的作用
            K k;            //同上
            //hash值相同，key也相同，那么就是更新这个键值对的值。同 jdk 1.7
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){ //注意在这个if内【e != null】
                e = p;//这地方，e = p  他们两个都是指向数组下标为i的地方，在这if else if else结束之后，再把节点的值value给更新了
            } else if (p instanceof TreeNode){  //这个树方法可能会返回null。
                //jdk 1.8引入了红黑树来处理碰撞，上面判断p的类型已经是树结构了，
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);//如果是，则走添加树的方法。
            } else {    //注意在这个else内，当为添加新节点时，【e == 】；更新某个节点时，就不是null
                for (int binCount = 0; ; ++binCount) {//还未形成树结构，还是jdk 1.7的链表结构
                    //差别就是1.7:是头插法，后来的留在数组上，先来的链在尾上；1.8:是先来的就留在数组上，后来的链在尾上
                    //判断p.next是否为空，同时为e赋值，若为空，则p.next指向新添加的节点，这是在链表长度小于7的时候
                    if ((e = p.next) == null) {
                        //这个地方有个不好理解的地方：在判断条件里面，把e指向p.next，也就是说现在e=null而不是下下一行错误的理解。
                        //这也就解释了更新的时候，返回oldValue，新建的时候，是不在那地方返回的。
                        p.next = newNode(hash, key, value, null);//e = p.next,p.next指向新生成的节点，也就是说e指向新节点（错误）
                        //对于临界值的分析：
                        //假设此次是第六次，binCount == 6,不会进行树变，当前链表长度是7；下次循环。
                        //binCount == 7，条件成立，进行树变，以后再put到这个桶的位置的时候，这个else就不走了，走中间的那个数结构的分叉语句啦
                        //这个时候，长度为8的链表就变成了红黑树啦
                        if (binCount >= TREEIFY_THRESHOLD - 1){// -1 for 1st //TREEIFY_THRESHOLD == 8
                            treeifyBin(tab, hash);
                        }
                        break;//插入新值或进行树变后，跳出for循环。此时e未重定向，还是指向null，虽然后面p.next指向了新节点。
                        //但是，跟e没关系。
                    }
                    //如果在循环链表的时候，找到key相同的节点，那么就跳出循环，就走不到链表的尾上了。
                    // e已经在上一步已经赋值了，且不为null,也会跳出for循环，会在下面更新value的值
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                        break;
                    }
                    //这个就是p.next也就是e不为空，然后，还没有key相同的情况出现，那就继续循环链表，
                    // p指向p.next也就是e，继续循环，继续，e=p.next
                    p = e;
                    //直到p.next为空，添加新的节点；或者出现key相等，更新旧值的情况才跳出循环。
                }
            }
            //经过上面if else if else之后，e在新建节点的时候，为null；更新的时候，则被赋值。在树里面处理putTreeVal（）同样如此，
            if (e != null) { // existing mapping for key//老外说的对，就是只有更新的时候，才走这，才会直接return oldValue
                V oldValue = e.value;
                //onlyIfAbsent 这个在调用hashMap的put()的时候，一直是false，那么下面更新value是肯定执行的
                if (!onlyIfAbsent || oldValue == null){
                    e.value = value;
                }
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold){
            resize();
        }
        afterNodeInsertion(evict);
        return null;

借用网上的图，先比较直观的看下这个转换过程：

    第一步：key值--->32位的哈希值
    这个就是key值调用hashCode()函数，生成一个32位的哈希值。
    第二步：32位哈希值--->混合哈希值
    这一步将32位哈希值的高16位与低16位做异或操作。为什么要这样做呢，因为后面还要进行一次indexFoe()操作截取低位信息（高位信息将会丢失），因此高低位异或操作后，低16位也能掺杂高16位的信息，高位的信息变相被保存下来了，可以增加随机性，减小冲突的可能性。
1,2两步的操作在put函数源码中合并成了一行代码，如下：

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    第三步：混合哈希值--->数组下标
链表数组的初始长度是16。显然这个32位的混合哈希值不能直接和链表数组直接对应起来，会照成大量冲突。这里采用了一次取模运算。HashMap 通过 hash 值与 length-1 (容器长度-1)进行取模（%）运算。可能有人会问：明明源码中 indexFor() 方法进行的 按位与（&）运算，而非取模运算。实际上，HashMap 中的 indexFor() 方法就是在进行取模运算。利用位运算代替取模运算，可以大大提高程序的计算效率。位运算可以直接对内存数据进行操作，不需要转换成十进制，因此效率要高得多。需要注意的是，只有在特定情况下，位运算才可以转换成取模运算（当 b = 2^n 时，a % b = a & (b - 1) ）。也是因此，HashMap 才将初始长度设置为 16，且扩容只能是以 2 的倍数（2^n）扩容。

在扩容操作时可能形成环形链表。
原因：
在HashMap扩容时，会改变链表中的元素的顺序，将元素从链表头部插入。（为了避免尾部遍历）。而环形链表就在这一时刻发生。添加元素时，如果超过阈值，就要进行扩容，如果两个元素同时添加，线程A和线程B可能同时扩容。线程A准备扩容时，线程B开始执行，扩容完毕，产生新的hashMap. 此时A—>Bnull变成B—>A null，先将A复制到新的hash表中，然后接着复制B到链头（A的前边：B.next=A），本来B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将B.next=A，所以，这里继续复制A，让A.next=B，由此，环形链表出现：B.next=A; A.next=B。本来应该通过 A.next=B来让A指向null 的，但是线程A已经把A.next变成B的位置了。所有行成回环。

因为hashSet底层也是利用hashMap实现的，所以这里一起分析下。
HashSet 是一个没有重复元素的集合，它是由HashMap实现的，不保证元素的顺序，而且HashSet允许使用 null 元素。
HashSet是非同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象，则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作，以防止对该 set 进行意外的不同步访问：Set s = Collections.synchronizedSet(new HashSet(...));

HashSet伪代码实现：

public class MyHashSet {
    private HashMap map;
    private static final Object PRESENT = new Object();
    public MyHashSet(){
        map = new HashMap();
    }
    public int size(){
        return map.size();
    }
    public void add(E e){
        map.put(e,PRESENT);
    }
    public void remove(E e){
        map.remove(e);
    }
}