【Java基础】HashMap解析

本文主要是介绍【Java基础】HashMap解析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、 哈希函数理解
如果我们自己要设计一个数据结构，首要任务是查询快，其次增删改快，怎么设计呢？

我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），所以我们要自己设计一个容器装数据，也得从这两个结构下手：

1. 顺序存储，这个代表的对象就是数组，内存直接分配一块连续的空间，在此基础上，只要你知道相对于数组第一个位置的下标，就能快速访问到想要的数据，非常快（例如：a[3]=5；），时间复杂度O（1），但是给定一个值让你找，那也只能遍历了，时间复杂度是O（n）。数组还有有个弱点，就是当你要在已有数据中间新增或者删除的时候，都会导致后续的元素平移，耗时，这不符合我们的预期。
2. 链式存储结构，其内存散碎在各处，每个元素通过存储自己前后邻居的位置，而你只知道住在第一家的位置，你想找任何一个人，唯一的方法就是一个一个问，这样查询的效率极低，时间复杂度是O（n），优势是你想插队或者删除一个，只要通知它左右邻居就可以，很方便。

因为我们首要任务是查询快，而顺序结构特点就是查询快，只要你能知道它的位置就能直接访问它的元素，所以主体我们选择顺序结构，但是实际工作中，我们都是直接按值查找，那不是没快么，如果有个算法，能根据值算出元素在数组中的位置就好了，这个算法其实就是哈希算法。

哈希算法：这个算法通俗来说就是把你要查找的内容翻译成位置。比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。这个函数可以简单描述为：存储位置 = f(关键字) ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。

整个过程有点像推币机：

只不过中间算法部分，被替换成了哈希算法，它会根据小球“key”的哈希，决定你在数组的哪个槽里。（如果按照当前算法，最后小球的落点是符合正态分布的），好的哈希算法，会精良把小球分散开来，不让他们落入同一个槽里，如果不幸落入同一个槽，那这就是哈希碰撞，也叫哈希冲突。

有了碰撞怎么处理呢，毕竟不能让一堆数据放到同一个地址里，处理哈希碰撞的方法有：
开放地址法：发生冲突，继续寻找下一块未被占用的存储地址。
再散列函数法：发生冲突就换一个散列函数，总有一个不碰撞的。
公共溢出区法：即为所有冲突的关键字建立一个公共的溢出区来存放，在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功，如果不相等，则到溢出表去进行顺序查找。
链地址法：把后续算出来同一个地址的小球（元素）用链表串起来，为什么用链表呢，因为方便增减，但是我们前面说过了，链表只能遍历查，所以要求这个链子不能太长，最多7个（jkd1.8），再长就转成红黑树。这个就是HashMap采用的方法。

二、 HashMap解析

1. put方法，可以理解往HashMap里放小球，一个小球对于HaspMap来说就是一个Node对象。

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

参数解析：
hash:key值算出来的hash值，这个就是我们上面说的，算位置。
key:这个就是存入数据的Key。
value:存入数据的value。
onlyIfAbsent：如果为true，则不更改现有值。（不知道干啥的）
evict：如果为false，则表处于创建模式。（不知道干啥的）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断当前map中的Node数组是不是空的，如果是空的，调用resize()方法，这个方法的作用是将Node数组大小初始化或加倍，这里用到的就是初始化。无论是不是第一次初始化，都要把最终数组也就是tab的长度赋值给n。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // (n - 1) & hash 这就是计算位置的算法，找到新存入Node的key的hash值，与数组长度-1相与，然后判断这个位置是否有值了。
        if ((p = tab[i = (n - 1) & hash]) == null)
        	//如果没有值，说明这个位置是空的，那直接new一个Node放到这个位置上。
            tab[i] = newNode(hash, key, value, null);
        else {
        	//如果不为空，说明碰撞了，在if中已经把这个位置已经存在的原有元素取出来，赋值给p，记住这个p是原来就有的节点啊。
            Node<K,V> e; K k;
            //判断p是不是就是新存入的这个元素，也就是同一个key，如果是的话就直接覆盖。
            if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
            	//如果不是，则判断p是不是一棵树的节点，如果是的话，那就走新增树节点的逻辑，把新加入的拼到红黑树上。
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            	//如果也不是树，那就肯定是链表了。遍历链表，把新的元素加到链表尾部。
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //TREEIFY_THRESHOLD是8，这里就是上文所说的，如果链表太长，会影响后续查询效率，所以过了7，就把链表转成红黑树。
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //这一步在HashMap没有实现，是为了LinkHashMap用的，为的是使用LRU算法。
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //如果没有碰撞，数据存入Node数组中了，那把数组size加一，然后跟阈值相比，HashMap默认阈值是最大size的四分之三，如果超了，触发扩容机制。
        if (++size > threshold)
            resize();
        //这一步在HashMap没有实现，是为了LinkHashMap用的，为的是使用LRU算法。
        afterNodeInsertion(evict);
        return null;
    }

扩容resize()：将表格大小初始化或加倍。如果为空，则根据字段阈值中保留的初始容量目标进行分配。否则，由于我们使用的是二次幂展开，每个bin中的元素必须保持在相同的索引中，或者在新表中以二次幂偏移量移动。
【未完待续。。。】

这篇关于【Java基础】HashMap解析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！