HashMap底层原理

标签: map  hashmap  扩容  底层原理

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 锁的方式是稍微细粒度的        Collections.synchronizedMap()方法可以获取一个线程安全的map

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

 

2、存储结构

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

 

 

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;

即使负载因子和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方法原理

1、判断键值对数组table[i]是否为空或为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进行频繁的扩容

原文链接:加载失败,请重新获取