中国移动 大数据平台 tensorflow 接口测试 node.js 拓展培训公司 Python爬虫实战 docker安装 sqlite session tkinter mongoose canvas angular ui router jtable vue案例 vue配置 npm安装vue web前端毕业设计题目 h5下拉刷新 input取消边框 git下载代码到本地命令 python界面 python中items python的open函数 python中的if语句 python的re模块 python处理json文件 java的string java集合 java基本类型 java基础学习 java字符串查找 java时间戳转时间 java数组添加值 java程序 java中instanceof java求阶乘 java中map java的框架
当前位置: 首页 > 学习教程  > 编程语言

HashMap底层实现和原理(源码解析)

2020/9/19 16:25:51 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Note:文章的内容基于JDK1.7进行分析,1.8做的改动文章末尾进行讲解。

大家可以看一下:https://www.imooc.com/article/267756

一、先来熟悉一下我们常用的HashMap

1、概述

HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null 建和null 值, 因为key不允许重复,因此只能有一个键为null,另外HashMap不能保证放入元素的顺序,它是无序的,和放入的顺序并不能相同。HashMap是线程不安全的。

2、继承关系

 
  1. public class HashMap<K,V>extends AbstractMap<K,V>

  2. implements Map<K,V>, Cloneable, Serializable

3、基本属性

 
  1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16

  2. static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子0.75

  3. static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默认数组

  4. transient int size; //HashMap中元素的数量

  5. int threshold; //判断是否需要调整HashMap的容量

Note:HashMap的扩容操作是一项很耗时的任务,所以如果能估算Map的容量,最好给它一个默认初始值,避免进行多次扩容。HashMap的线程是不安全的,多线程环境中推荐是ConcurrentHashMap。

二、常被问到的HashMap和Hashtable的区别

1、线程安全

两者最主要的区别在于Hashtable是线程安全,而HashMap则非线程安全。

Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高一些,我们平时使用时若无特殊需求建议使用HashMap,在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

Note:

Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类,这个类实现了Map接口,在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例,简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步,类似的其它Collections.synchronizedXX方法也是类似原理。

2、针对null的不同

HashMap可以使用null作为key,而Hashtable则不允许null作为key
虽说HashMap支持null值作为key,不过建议还是尽量避免这样使用,因为一旦不小心使用了,若因此引发一些问题,排查起来很是费事。
Note:HashMap以null作为key时,总是存储在table数组的第一个节点上。

3、继承结构

HashMap是对Map接口的实现,HashTable实现了Map接口和Dictionary抽象类。

4、初始容量与扩容

HashMap的初始容量为16,Hashtable初始容量为11,两者的填充因子默认都是0.75。

HashMap扩容时是当前容量翻倍即:capacity*2,Hashtable扩容时是容量翻倍+1即:capacity*2+1。

5、两者计算hash的方法不同

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

 
  1. int hash = key.hashCode();

  2. int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap计算hash对key的hashcode进行了二次hash,以获得更好的散列值,然后对table数组长度取摸。

 
  1. int hash = hash(key.hashCode());

  2. int i = indexFor(hash, table.length);

  3.  
  4. static int hash(int h) {

  5. // This function ensures that hashCodes that differ only by

  6. // constant multiples at each bit position have a bounded

  7. // number of collisions (approximately 8 at default load factor).

  8. h ^= (h >>> 20) ^ (h >>> 12);

  9. return h ^ (h >>> 7) ^ (h >>> 4);

  10. }

  11.  
  12. static int indexFor(int h, int length) {

  13. return h & (length-1);

三、HashMap的数据存储结构

1、HashMap由数组和链表来实现对数据的存储

HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体,以此来解决Hash冲突的问题。

数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

 

 

 

从上图我们可以发现数据结构由数组+链表组成,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key.hashCode())%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap里面实现一个静态内部类Entry,其重要的属性有 hash,key,value,next。

HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。

 
  1. public V put(K key, V value) {

  2. if (key == null)

  3. return putForNullKey(value); //null总是放在数组的第一个链表中

  4. int hash = hash(key.hashCode());

  5. int i = indexFor(hash, table.length);

  6. //遍历链表

  7. for (Entry<K,V> e = table[i]; e != null; e = e.next) {

  8. Object k;

  9. //如果key在链表中已存在,则替换为新value

  10. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

  11. V oldValue = e.value;

  12. e.value = value;

  13. e.recordAccess(this);

  14. return oldValue;

  15. }

  16. }

  17.  
  18. modCount++;

  19. addEntry(hash, key, value, i);

  20. return null;

  21. }

  22.  
  23.  
  24.  
  25. void addEntry(int hash, K key, V value, int bucketIndex) {

  26. Entry<K,V> e = table[bucketIndex];

  27. table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next

  28. //如果size超过threshold,则扩充table大小。再散列

  29. if (size++ >= threshold)

  30. resize(2 * table.length);

  31. }

四、重要方法深度解析

1、构造方法

 
  1. HashMap() //无参构造方法

  2. HashMap(int initialCapacity) //指定初始容量的构造方法

  3. HashMap(int initialCapacity, float loadFactor) //指定初始容量和负载因子

  4. HashMap(Map<? extends K,? extends V> m) //指定集合,转化为HashMap

HashMap提供了四个构造方法,构造方法中 ,依靠第三个方法来执行的,但是前三个方法都没有进行数组的初始化操作,即使调用了构造方法此时存放HaspMap中数组元素的table表长度依旧为0 。在第四个构造方法中调用了inflateTable()方法完成了table的初始化操作,并将m中的元素添加到HashMap中。

2、添加方法

 
  1. public V put(K key, V value) {

  2. if (table == EMPTY_TABLE) { //是否初始化

  3. inflateTable(threshold);

  4. }

  5. if (key == null) //放置在0号位置

  6. return putForNullKey(value);

  7. int hash = hash(key); //计算hash值

  8. int i = indexFor(hash, table.length); //计算在Entry[]中的存储位置

  9. for (Entry<K,V> e = table[i]; e != null; e = e.next) {

  10. Object k;

  11. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

  12. V oldValue = e.value;

  13. e.value = value;

  14. e.recordAccess(this);

  15. return oldValue;

  16. }

  17. }

  18.  
  19. modCount++;

  20. addEntry(hash, key, value, i); //添加到Map中

  21. return null;

  22. }

在该方法中,添加键值对时,首先进行table是否初始化的判断,如果没有进行初始化(分配空间,Entry[]数组的长度)。然后进行key是否为null的判断,如果key==null ,放置在Entry[]的0号位置。计算在Entry[]数组的存储位置,判断该位置上是否已有元素,如果已经有元素存在,则遍历该Entry[]数组位置上的单链表。判断key是否存在,如果key已经存在,则用新的value值,替换点旧的value值,并将旧的value值返回。如果key不存在于HashMap中,程序继续向下执行。将key-vlaue, 生成Entry实体,添加到HashMap中的Entry[]数组中。

3、addEntry()

 
  1. /*

  2. * hash hash值

  3. * key 键值

  4. * value value值

  5. * bucketIndex Entry[]数组中的存储索引

  6. * /

  7. void addEntry(int hash, K key, V value, int bucketIndex) {

  8. if ((size >= threshold) && (null != table[bucketIndex])) {

  9. resize(2 * table.length); //扩容操作,将数据元素重新计算位置后放入newTable中,链表的顺序与之前的顺序相反

  10. hash = (null != key) ? hash(key) : 0;

  11. bucketIndex = indexFor(hash, table.length);

  12. }

  13.  
  14. createEntry(hash, key, value, bucketIndex);

  15. }

  16. void createEntry(int hash, K key, V value, int bucketIndex) {

  17. Entry<K,V> e = table[bucketIndex];

  18. table[bucketIndex] = new Entry<>(hash, key, value, e);

  19. size++;

  20. }

添加到方法的具体操作,在添加之前先进行容量的判断,如果当前容量达到了阈值,并且需要存储到Entry[]数组中,先进性扩容操作,空充的容量为table长度的2倍。重新计算hash值,和数组存储的位置,扩容后的链表顺序与扩容前的链表顺序相反。然后将新添加的Entry实体存放到当前Entry[]位置链表的头部。在1.8之前,新插入的元素都是放在了链表的头部位置,但是这种操作在高并发的环境下容易导致死锁,所以1.8之后,新插入的元素都放在了链表的尾部。

4、获取方法:get

 
  1. public V get(Object key) {

  2. if (key == null)

  3. //返回table[0] 的value值

  4. return getForNullKey();

  5. Entry<K,V> entry = getEntry(key);

  6.  
  7. return null == entry ? null : entry.getValue();

  8. }

  9. final Entry<K,V> getEntry(Object key) {

  10. if (size == 0) {

  11. return null;

  12. }

  13.  
  14. int hash = (key == null) ? 0 : hash(key);

  15. for (Entry<K,V> e = table[indexFor(hash, table.length)];

  16. e != null;

  17. e = e.next) {

  18. Object k;

  19. if (e.hash == hash &&

  20. ((k = e.key) == key || (key != null && key.equals(k))))

  21. return e;

  22. }

  23. return null;

  24. }

在get方法中,首先计算hash值,然后调用indexFor()方法得到该key在table中的存储位置,得到该位置的单链表,遍历列表找到key和指定key内容相等的Entry,返回entry.value值。

5、删除方法

 
  1. public V remove(Object key) {

  2. Entry<K,V> e = removeEntryForKey(key);

  3. return (e == null ? null : e.value);

  4. }

  5. final Entry<K,V> removeEntryForKey(Object key) {

  6. if (size == 0) {

  7. return null;

  8. }

  9. int hash = (key == null) ? 0 : hash(key);

  10. int i = indexFor(hash, table.length);

  11. Entry<K,V> prev = table[i];

  12. Entry<K,V> e = prev;

  13.  
  14. while (e != null) {

  15. Entry<K,V> next = e.next;

  16. Object k;

  17. if (e.hash == hash &&

  18. ((k = e.key) == key || (key != null && key.equals(k)))) {

  19. modCount++;

  20. size--;

  21. if (prev == e)

  22. table[i] = next;

  23. else

  24. prev.next = next;

  25. e.recordRemoval(this);

  26. return e;

  27. }

  28. prev = e;

  29. e = next;

  30. }

  31.  
  32. return e;

  33. }

删除操作,先计算指定key的hash值,然后计算出table中的存储位置,判断当前位置是否Entry实体存在,如果没有直接返回,若当前位置有Entry实体存在,则开始遍历列表。定义了三个Entry引用,分别为pre, e ,next。 在循环遍历的过程中,首先判断pre 和 e 是否相等,若相等表明,table的当前位置只有一个元素,直接将table[i] = next = null 。若形成了pre -> e -> next 的连接关系,判断e的key是否和指定的key 相等,若相等则让pre -> next ,e 失去引用。

6、containsKey

 
  1. public boolean containsKey(Object key) {

  2. return getEntry(key) != null;

  3. }

  4. final Entry<K,V> getEntry(Object key) {

  5. int hash = (key == null) ? 0 : hash(key.hashCode());

  6. for (Entry<K,V> e = table[indexFor(hash, table.length)];

  7. e != null;

  8. e = e.next) {

  9. Object k;

  10. if (e.hash == hash &&

  11. ((k = e.key) == key || (key != null && key.equals(k))))

  12. return e;

  13. }

  14. return null;

  15. }

containsKey方法是先计算hash然后使用hash和table.length取摸得到index值,遍历table[index]元素查找是否包含key相同的值。

7、containsValue

 
  1. public boolean containsValue(Object value) {

  2. if (value == null)

  3. return containsNullValue();

  4.  
  5. Entry[] tab = table;

  6. for (int i = 0; i < tab.length ; i++)

  7. for (Entry e = tab[i] ; e != null ; e = e.next)

  8. if (value.equals(e.value))

  9. return true;

  10. return false;

  11. }

containsValue方法就比较粗暴了,就是直接遍历所有元素直到找到value,由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别,你别指望它会像containsKey那么高效。

五、JDK 1.8的 改变

1、HashMap采用数组+链表+红黑树实现。

在Jdk1.8中HashMap的实现方式做了一些改变,但是基本思想还是没有变得,只是在一些地方做了优化,下面来看一下这些改变的地方,数据结构的存储由数组+链表的方式,变化为数组+链表+红黑树的存储方式,当链表长度超过阈值(8)时,将链表转换为红黑树。在性能上进一步得到提升。

2、put方法简单解析:

 
  1. public V put(K key, V value) {

  2. //调用putVal()方法完成

  3. return putVal(hash(key), key, value, false, true);

  4. }

  5.  
  6. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

  7. boolean evict) {

  8. Node<K,V>[] tab; Node<K,V> p; int n, i;

  9. //判断table是否初始化,否则初始化操作

  10. if ((tab = table) == null || (n = tab.length) == 0)

  11. n = (tab = resize()).length;

  12. //计算存储的索引位置,如果没有元素,直接赋值

  13. if ((p = tab[i = (n - 1) & hash]) == null)

  14. tab[i] = newNode(hash, key, value, null);

  15. else {

  16. Node<K,V> e; K k;

  17. //节点若已经存在,执行赋值操作

  18. if (p.hash == hash &&

  19. ((k = p.key) == key || (key != null && key.equals(k))))

  20. e = p;

  21. //判断链表是否是红黑树

  22. else if (p instanceof TreeNode)

  23. //红黑树对象操作

  24. e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

  25. else {

  26. //为链表,

  27. for (int binCount = 0; ; ++binCount) {

  28. if ((e = p.next) == null) {

  29. p.next = newNode(hash, key, value, null);

  30. //链表长度8,将链表转化为红黑树存储

  31. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

  32. treeifyBin(tab, hash);

  33. break;

  34. }

  35. //key存在,直接覆盖

  36. if (e.hash == hash &&

  37. ((k = e.key) == key || (key != null && key.equals(k))))

  38. break;

  39. p = e;

  40. }

  41. }

  42. if (e != null) { // existing mapping for key

  43. V oldValue = e.value;

  44. if (!onlyIfAbsent || oldValue == null)

  45. e.value = value;

  46. afterNodeAccess(e);

  47. return oldValue;

  48. }

  49. }

  50. //记录修改次数

  51. ++modCount;

  52. //判断是否需要扩容

  53. if (++size > threshold)

  54. resize();

  55. //空操作

  56. afterNodeInsertion(evict);

  57. return null;

  58. }

如果存在key节点,返回旧值,如果不存在则返回Null。


本文链接: http://www.dtmao.cc/news_show_200423.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?