HashMap底层原理

￡神魔★判官ぃ 2021-10-14 22:55 583阅读 0赞

## 1、java.util.Map的实现类HashMap、Hashtable、LinkedHashMap、TreeMap、ConcurrentHashMap之间的关系 ##

1、HashMap与HashTable的区别？  
    HashMap线程不安全，Hashtable线程安全  
    HashMap允许K/V都为null；后者K/V都不允许为null  
    HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类  
2、ConcurrentHashMap和Hashtable的区别？  
    ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。  
    但是 HashTable 在每次同步执行时都要锁住整个结构，ConcurrentHashMap 锁的方式是稍微细粒度的

3、同步集合与并发集合？

Collections.synchronizedMap()方法可以获取一个线程安全的map，称为同步集合，锁住整个方法（粗粒度）

ConcurrentHashMap 是并发集合，锁是细粒度的

ConcurrentHashMap，它内部细分了若干个小的HashMap，称之为段(Segment)。默认情况下一个ConcurrentHashMap被进一步细分为16个段，既就是锁的并发度（分段锁）

不管是同步集合还是并发集合，都能保证线程安全，但建议使用并发集合

3、LinkedHashMap按插入顺序存储，TreeMap可对键排序

## 2、存储结构 ##

java7采用数组+单向链表，java8采用数组+单向链表+红黑树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 1][]

HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都有一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上 。

Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞

几个字段：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16 
    int threshold; // 所能容纳的key-value对极限，threshold = length * loadFactor，length默认16，
                      当超过threshold就要扩容，length就是Entry数组的长度，一定是2的n次方，即每次扩容一倍
    final float loadFactor; // 负载因子，默认0.75
    int modCount; //记录HashMap内部结构发生变化的次数
    int size; //实际存储的kv对个数

即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能

## 3、内部功能 ##

### 1、根据key获取哈希桶数组索引位置 ###

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算

源码的实现(方法一+方法二):
    
    //方法一：jdk1.8 & jdk1.7
    static final int hash(Object key) { 
       
        //key.hashCode()    第一步.取hashCode值
        //h >>> 16          第二步.高位参与运算
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    
    //方法二：jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
    static int indexFor(int h, int length) { 
        //第三步.取模运算，相当于h%length,但效率更高
        return h & (length-1);
    }

### 2、put方法原理 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 2][]

注：table就是数组，table\[i\]就是数组的第i个元素

1、判断键值对数组table是否为空或为null，否则执行resize()进行扩容；

2、根据键值key计算hash值得到插入的数组索引i，如果table\[i\]==null，直接新建节点添加，转向6，如果table\[i\]不为空，转向3

3、判断table\[i\]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashCode以及equals

4、判断table\[i\] 是否为treeNode，即table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5

5、遍历table\[i\]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可

6、插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容

###  3、扩容机制 ###

数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组

扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容

### 4、为什么哈希桶数组大小是2的n次幂 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 3][]

### 5、为什么链表长度超过8就转化为红黑树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 4][]

### 6、hashmap的key为自定义对象时，要重写equals和hashcode方法 ###

因为hashmap是根据哈希值计算的，当自定义对象的属性完全相同，但hashcode可能不同，因此要重写hashcode方法。重写hashcode则equals必须重写

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70]: /images/20211015/6895e7c5fd0d469d9c701ff1f0f03a2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 1]: /images/20211015/46f193a862734af39e1c74a3ba9461a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 2]: /images/20211015/cd9166cbf0974a00b623179c5839cbd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 3]: /images/20211015/04cfd250e0a944b9885adb13f71f0688.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70 4]: /images/20211015/e5c58324ac9640a690541ee1fcb53848.png