黑马程序员技术交流社区

标题: HashMap底层原理 [打印本页]

---

作者: 没有bug    时间: 2019-10-10 14:20
标题: HashMap底层原理
一、前置名词解释
（1）哈希表
哈希表的主体躯干就是数组，我们可以利用下标对元素进行快速索引。新增一个元素时，元素的插入位置由哈希函数来定。
（2）哈希算法/哈希函数
哈希函数的作用是将一个不固定长度的二进制值经过运算，转化为一个固定长度的二进制值。将插入元素的key进行运算后，得到某个index值，从而确定在数组中的存储位置。但多个不相同的元素，经过哈希函数运算后，可能得到相同的index，这就出现了哈希冲突。
（3）哈希冲突/哈希碰撞
再好的哈希算法在有限长度的哈希表上，都会造成哈希冲突。那么怎么解决冲突呢？有多种解决方案
【1】开放地址法：放弃本次运算得到的index，继续寻找下一块未被占用的空间
【2】再散列法
【3】链地址法：采用数组（哈希表主体）+链表（为了解决哈希冲突而存在）的形式，哈希表中存储数组，数组中的元素空间存储链表的头结点。当发生冲突时，将相应的index位置上旧元素的指针next指向新元素即可。HashMap采用的就是这种方法。
二、HashMap的特点
（1）允许存放null键和null值，而HashTable都不允许
（2）不是线程安全的，而HashTable是线程安全的，当然我们可以使用ConcurrentHashMap来代替HashTable,而且ConcurrentHashMap的性能更好，因为它只对数组的一部分进行上锁，即分段锁，而不是锁住整个数组。
（3）数组的默认大小为16，源码中没有直接写16，而是1<<4。
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
（4）默认的负载因子是0.75，表示的是，如果数组中已经存储的元素个数大于数组长度的75%，将会引发扩容操作。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
（5）扩容后，新数组的长度为原来数组的两倍。数组的默认大小与扩容倍数共同决定了数组长度永远是一个2的幂。
三、HashMap的实现原理
（1）HashMap的主干
HashMap的主干是一个Entry数组，里面存放Entry对象，每一个Entry对象包含（key,value）键值対和next指针以及对应的hash值。[jdk1.8之前用的是Entry，jdk1.8之后用的是Node，两者基本等价]
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
      .........
}
（2）put（key，value）的过程
【1】由key计算哈希值
【2】由哈希值计算在数组中的索引
【3】如果索引处的Entry为null的话，则直接在此处插入元素。如果索引出的Entry不为null的话，通过循环不断遍历链表查找是否有相同哈希值的key，如果有，再比较两个key的是否相同，当哈希值与key都相同时，则认为是同一个Entry对象并覆盖原对象的value值。当哈希值相同而key不相同时，则认为不是同一个Entry对象，那么在链表尾部新增元素。[jdk1.8之前插入链表头部，jdk1.8之后插入链表尾部]
当索引位置相同的key超过8个时，即链表长度大于8时，jdk1.8会将此链表转化为红黑树。
（3）get（key）的过程
【1】由key计算哈希值
【2】由哈希值计算在数组中的索引
【3】循环遍历链表，如果有某一个Entry的key与哈希值与搜索的key、哈希值都相同的话，则取出此key对应的value。
（4）扩容的过程
当数组中已经存储的元素个数大于数组长度的负载因子倍数时，将会引发扩容操作。
【1】创建一个长度为原来数组长度两倍的新数组。
【2】重新对原数组中的Entry对象进行哈希运算，以确定他们各自在新数组中的新位置。

---

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

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