高效编程之hashmap你必须要懂的知识点

以前看Java的招聘要求:Java基础扎实,熟悉常用集合类,多线程,IO,网络编程,经常会疑惑,集合类不就ArrayList,HashMap会用,熟悉下API不就好了么,知道得越多才会发觉不知道的还有好多!     一入Java深似海啊

本文使用的源码是jdk1.7的源码,hashmap每个版本都发生了改变,源码都不同,但原理都是一样的,可以参考一下;

读下文前可以先思考以下这几个问题,带着问题去阅读,收获更大;

1、平时我为什么要用hashmap?key和value是以什么样的形式存在的?

2、我了解hashmap的内部结构和实现原理吗?

3、hashmap构造方法的参数有哪些,有什么用?

4、用hashmap的时候需不需要给他一个初始化大小?如果要该怎么定义?

5、不起眼的hashcode和equals方法为什么在hashmap中至关重要?

6、什么是哈希冲突?发生哈希冲突好还是不好?不好该怎么解决?

7、hashmap有什么缺点?它跟hashtable有什么性能区别?

从下面的两张图可以看到,hashmap是由数组和链表组成的;

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

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

哈希表:这时候该引出哈希表了,哈希表寻址容易,插入删除也容易,同事还满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便!简直牛逼啊~

先盗两张图...因为我不会画...

hashmap是基于Map接口实现、允许null键/值、非同步这个大家应该都是知道的... 这个时候应该对hashmap有个感性的认识了

那我们从API里面来看看hashmap的构造方法,初始一下  initialCapacity 和 loadFactor 两个名词:

HashMap() 构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空HashMap。

HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空HashMap。

HashMap(int initialCapacity, float loadFactor)  构造一个带指定初始容量和加载因子的空HashMap。

initialCapacity是哈希表的数组的初始大小,loadFactor是加载因子;

HashMap的默认大小是16,那么他的数组长度就是0-15;默认加载因子是0.75;

为什么是16呢不是其他的数字呢?为什么默认的加载因子是0.75呢? 留个悬念哈~后面会提到的!

我们可以看到hashmap里面存放的是一个一个的Entry对象,(下文中的entry/entry对象即为此处的Entry对象)

我们看看看看hashmap是如何定义的Entry对象;

[java] view plain copy

  1. static class Entry<K,V> implements Map.Entry<K,V> {  
  2. final K key;  
  3.        V value;  
  4.        Entry<K,V> next;  
  5. int hash;  
  6. /**
  7.         * Creates new entry.
  8.         */
  9.        Entry(int h, K k, V v, Entry<K,V> n) {  
  10.            value = v;  
  11.            next = n;  
  12.            key = k;  
  13.            hash = h;  
  14.        }  

上面这是Entry对象的部分代码;

final K key :表示key是不能改变的  final关键字!

value:这没啥好说的;

Entry<k,v> next 指向下一个节点;

int hash: 这个hash 是一个散列码 是这样得到的:int hash = hash(key.hashcode());下文会有详细讲解~

重点部分来了!

HashMap的put方法:

put方法大致的思路是: 1、对key的hashCode()做hash,然后再计算存到数组里的下标; 2、如果没发生冲突直接放到数组里; 3、如果冲突了,以链表的形式存在对应的数组[ i ]中 ; 4、如果冲突导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树; 5、如果节点已经存在就替换old value(保证key的唯一性) 6、如果数组满了(超过load factor*current capacity),就要resize(扩容)。

[java] view plain copy

  1. public V put(K key, V value) {  
  2. if (key == null)  
  3. return putForNullKey(value);  
  4. int hash = hash(key);  
  5. int i = indexFor(hash, table.length);  
  6. for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  7.             Object k;  
  8. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  9.                 V oldValue = e.value;  
  10.                 e.value = value;  
  11.                 e.recordAccess(this);  
  12. return oldValue;  
  13.             }  
  14.         }  
  15.         modCount++;  
  16.         addEntry(hash, key, value, i);  
  17. return null;  
  18.     }  

这是jdk1.7的源码,1.8只是多了一个新特性,当链表的长度>7的时候,链表转换为红黑树提高查询的效率;

代码有注释,我这里再分析一次;首先通过key.hashcode()出哈希码,哈希码拿去做hash运算算出一个散列值,散列值(hash)跟数组的长度做indexFor运算,就得到了一个entry对象要存到数组的下标,这里有一个要点! 就是这个hash运算的算法设计,因为就算你拿不同的key去调用hashcode方法得到不同的值拿去做hash运算都会得到一个相同的值,然后把相同的散列值拿去做indexFor运算就会得到相同的 i ,这就发生了哈希表的冲突~~ 发生冲突了怎么办呢?

这里解释源码里的 if 中的判断,因为hash(散列值)是会算出重复的(冲突嘛~),如果这个Entry对象的hash(散列值)和你拿进来的key算的散列值(hash=hash(key))是一样的并且key也相等(==),那么你放进来的这个entry对象是同一个对象,hashmap允许你的key为空,但是key不能相同,所以新进来的会覆盖旧的;或者key.equals(k),如果这两个对象通过hashmap重写的equals方法判断是一样的,那也说明是同一个entry对象嘛!怎么办? 老办法,新的覆盖旧的!其他发生冲突的情况就把新加入的entry对象放到对应数组下标位置的表头,早进来的entry对象后移一个位置,这就形成了一个链表~~

好的,上面说的挺啰嗦的,下面来个1.8版本的总结,1.8跟1.7差不多~,1.8只是多了一个新特性,当链表的长度>=8的时候,链表转换为红黑树提高查询的效率;

[java] view plain copy

  1. 1.8 链表转红黑树的源码  
  2. static final int TREEIFY_THRESHOLD = 8;  
  3. if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  4.          treeifyBin(tab, hash);  
  5. break;  

扩容的源码:

添加entry对象的时候如果会时刻判断需不需要扩容数组

[java] view plain copy

  1. void addEntry(int hash, K key, V value, int bucketIndex) {  
  2. if ((size >= threshold) && (null != table[bucketIndex])) {  
  3.             resize(2 * table.length);  
  4.             hash = (null != key) ? hash(key) : 0;  
  5.             bucketIndex = indexFor(hash, table.length);  
  6.         }  
  7.         createEntry(hash, key, value, bucketIndex);  
  8.     }  

threshold是一个域值:是由现在的数组容量*加载因子;比如初始容量是16,加载因子是0.75;那么threshold=16*0.75=12; 当数组.size达到12的时候就会扩容了,

会把数组的大小从16扩容到32,那么这时的情况就是,哈希表的数组有第12个元素时,数组就会扩容到32;

[java] view plain copy

  1. void resize(int newCapacity) {  
  2.       Entry[] oldTable = table;  
  3. int oldCapacity = oldTable.length;  
  4. if (oldCapacity == MAXIMUM_CAPACITY) {  
  5.           threshold = Integer.MAX_VALUE;  
  6. return;  
  7.       }  
  8.       Entry[] newTable = new Entry[newCapacity];  
  9. boolean oldAltHashing = useAltHashing;  
  10.       useAltHashing |= sun.misc.VM.isBooted() &&  
  11.               (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
  12. boolean rehash = oldAltHashing ^ useAltHashing;  
  13.       transfer(newTable, rehash);  
  14.       table = newTable;  
  15.       threshold = (int)(newCapacity * loadFactor);  
  16.   }  

new Capacity 就是那个两倍的数组对象,(上面的2*table.length);

transf(newTable,rehash)这个方法是把原来那个未扩容前数组里的所有entry对象复制到现在这个新数组中来;

此时的域值  threshold 的大小就是新的数组大小 * 0.75 ;

说完put,说get~

[java] view plain copy

  1. public V get(Object key) {  
  2. if (key == null)  
  3. return getForNullKey();  
  4. int hash = hash(key.hashCode());  
  5. //先定位到数组元素,再遍历该元素处的链表
  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 && ((k = e.key) == key || key.equals(k)))  
  11. return e.value;  
  12.        }  
  13. return null;  

分析完put,get就容易理解多了~

key==null,这个情况不用讲了吧~

还是先算出散列码的值,然后通过散列码定位到数组(table)下标,也就是常说的通过key就可以拿到value,hashmap底层都是通过key拿到entry对象,然后直接从entry对象里拿到value的;

接着说:如果通过key找到了entry对象,进入if判断,第一种情况:如果entry对象的散列码和 传进来key的散列码是相等(都是int嘛,直接判断是否相等)并且entry对象的key和你传进来的key如果也相等那么就认为是你的key跟你要找的key是同一个,那么就直接return你要的value; 哦对了,这个Object  k,是为了去接收entry对象的key(然后赋值给object的k)然后才好和你传进来的key做比较,因为人家不知道你传进来的是什么类型的嘛,用object比就不会有类型转换的错误; 第二种情况:如果e.hash == hash 然后你传进来的key和entry对象的key连重写后的equals后都一样,那肯定就是同一个key了嘛;

不知道我这个菜鸟分析得怎么样,不过可以通过以下几个问题来加深对HashMap的理解;

1. 什么时候会使用HashMap?他有什么特点?

是基于Map接口的实现,存储键值对时,它可以接收null的键值,是非同步的线程不安全,HashMap存储着Entry(hash, key, value, next)对象。

2. 你知道HashMap的工作原理吗? 通过hash的方法,通过put和get存储和获取对象。存储对象时,我们将key传给put方法时,它调用hashCode计算hash从而得到储存的数组下标位置,进一步存储,HashMap会根据当前数组的占用情况自动调整容量(超过域值时则resize为原来的2倍)。获取对象时,我们将key传给get方法,它调用hashCode计算hash从而得到数组下标位置,并进一步调用equals()方法确定键值对。如果发生冲突的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个数组中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

3.为什么要重写hashcode和equals方法?

1、因为要得到散列码(hash)的时候要通过key.hashcode()去得到key的哈希码才可以做hash运算;不论是put和get方法,都要使用equals方法,equals方法是object的一个方法,直接调用是比较内存(object.equals源码是用==做比较);

2、Java约定在用集合类中要重写hashcode和equals方法;  Effective java 这本书第二章有详细的解释为什么要定义这样的公约,感兴趣的可以去看看;

4、 为什么HashMap的初始大小是16?为什么默认的加载因子是0.75?HashMap的大小超过了加载因子定义的容量,怎么办?

16是2的4次方,hashmap在put的时候会发生冲突,hashmap发生冲突是不可避免的,也是我们想要的,但是我们不想hashmap傻不拉几的发生冲突,因为最坏的情况,hashmap所有的冲突都发生在同一个数组下标的话,这个位置的链表过长,而其他数组位置确实空的,这样又hashmap还扩容不了,链表的查询效率可想而知,这样的话hashmap还有那么牛逼吗?把数组的长度设计成为2的n次方,加载因子设计为0.75,会极大的优化冲突,使每个数组的链表都差不多长(也不一定,概率问题);

至于为什么? 这是数据结构相关的东西,当时是数学家设计的啊,你问我怎么知道的? 不记得什么时候看了篇论文还是博客,上面是这样说的~我真的印象很深的记得我看到过,如果你不信也没办法~  反正是有这么回事

如果超过了负载因子,则会重新resize一个原来长度两倍的HashMap。

5、如果两个键的hashcode相同,你如何获取对象的值?

获取对象的值,那么就是get方法咯,两个key的hashcode相同说明 散列码(hash)相同,

如果散列码都相同了,那么就会调用key.equals()去判断在该散列码得到的这个数组下标的链表里的entry对象是否有相同的对象;

如果有,那么好,你直接拿这个entry对象的值即可;

6、用hashmap的时候需不需要给他一个初始化大小?如果要该怎么定义?

此问题是博主自己想出来的,答案也是博主自己思考的一个结果,不一定对,提供一个思路!如果你有更好的回答,可以留言给我一起探讨,谢谢啦~

最好是需要的,因为我们知道hashmap的数组长度超过了他的域值会扩容,扩容的时候会把hashmap中所有的entry对象再计算一次他们在新数组中的下标;可以想象一下,如果一个hashmap里有10万个entry对象了,如果要扩容,这10万个entry对象的位置都要发生变化,这会有多影响系统性能?不优化一下吗?   如何定义这个我也回答不了...因为我们只能初始化数组的大小,并不会知道每个数组元素的链表会有多长,我看同事他们创建hashmap的时候好像都没有给参数,那么如果这10万条数据放到一个大小为16的hashmap里,如果不扩容的话10万条数据只放在数组的11个元素中,那平均每个链表长度有接近1W,肯定不合理吗,链表的查询速度那么慢,所以我们判断必定会扩容,好!我们知道会扩容,但不知道会扩容几次啊,这里就是这个问题难的地方了,因为我们无法知道hashmap会扩容多少次,我们能做的就是减少他扩容的次数,同时又不让hashmap占太多内存~ 那我们就大胆的预测吧,比如有10万条数据,我觉得至少hashmap数组长度应该给1W吧,这样我们就可以把hashmap的初始大小定义为2的14次方 16384,这样数组的长度我们就定义了1.6W,就算用了1W个,也不会扩容,也没浪费更多的资源;如果你觉得10万条数据可能用不到1W个数组这么长,那你就把hashmap的初始大小定义为2的13次方,或者2的12次方;我们开始就定义一个大小总比我们不定义好(毕竟默认只有16)对吧?

7、我们可以用自定义的对象作为hashmap的key吗?如果可以,你会自定义对象当做key吗?如果不行说明原因。

可以使用自定义的对象作为hashmap的key,只要重写hashcode和equals方法就可以了,原因见第三个问题的回答;

但我一般不会把自定义对象作为key,因为有Integer跟string给我用,没必要使用自定义对象了,复杂,麻烦~

8、那你平时使用hashmap的时候一般用什么当做key,为什么?

Integer跟string呀,因为用他们用起来简单啊,Entry对象的四个属性中key是被final关键字修饰的,而Integer和string都是不可变的,直接使用Integer和string岂不美哉

9、hashmap并不能保证线程安全,如果要保证线程安全怎么办?

hashtable能保证线程安全,但有一种更高效的方式就是使用CocurrentHashMap来保证线程安全,同时效率又高;

hashtable是锁住整个数组,一次只能有一个线程去hashtable里面拿,而CocurrentHashMap是只锁数组[ i ] ,所以CocurrentHashMap的效率会比hashtable快很多,又比hashmap安全性要高,实在是居家旅行之首选~

10、那你还知道什么类似hashmap的东西吗?

有个安卓的大牛告诉我有 SarseArray  , 安卓内部特有的一个API,因为hashmap用entry来保存key和value,这里entry涉及自动装箱和拆箱,其实挺占内存的;在key为Integer的场景可以使用SarseArray;(后半段来自搜索的解释)假设现在有这样的情况,我们定义了一个长度为100的数组,虚拟机为我们开辟了100个单位的内存空间,但是我们只使用了很少(假设是5个)的一些单元,这样就造成了内存空间的浪费。而 SparseArray 是一个优化的数组,它的 key 是 Integer 类型而不是其他类型,是因为这个数组是按照 key 值的大小来排序的。按照 key 值大小排序的好处是查找的时候,可以使用二分查找,而不是蛮力的遍历整个数组。这也是为什么 SparseArray 适合替换 HashMap<Integer,<E>>,而不是任何 HashMap 的原因了。在这种情况下,原本需要100个单位内存空间而 SparseArray 只占用了5个单位的内存(实际比5个单位要大一些,因为还有一些逻辑控制的内存消耗)。key 值被当成了数组下标的功能来使用了。 安卓用SarseArray 很大一部分原因就是因为 SarseArray 比较节约内存;

结语:写博客是个自我总结的过程,其实这些知识点网上都有,随便Google一下一把大,很多牛人都深入研究过hashmap,我写的这些东西也都是看了上百篇别人的博客总结下来的,因为自己在hashmap上以前花了很多时间去学习,但过一阵子遇到某个细节点的问题的时候总感觉不太记得了;这次为了写这个博客,花了6-7个小时,这个过程让我加深了记忆,可能这几年都不会忘掉这些了,下次用到hashmap的时候可以瞬间就想起这些;

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

Python编程一定要注意的那些“坑”(九):0与False

问题描述:在编程时,经常需要单独编写一个函数用来判断某个事件是否成立,如果成立就返回正常结果,否则返回False。在主调函数中根据被调函数的返回值决定下一步的操...

1173
来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2785
来自专栏程序员互动联盟

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

3228
来自专栏数据魔术师

基础算法 | 数据结构之线性表&顺序表&链表(上)

各位,起床了起床了 小编又来送干货了 今天讲的是数据结构 全文字数:1185字 阅读时间:10分钟 数据结构?啥玩意? * 内容提要: *预备知识 *顺序表(S...

4066
来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2896
来自专栏互扯程序

Java开发中遇到的那些坑!

之前在这个手册刚发布的时候看过一遍,当时感觉真是每个开发者都应该必读的一本手册,最近由于在总结一些我们日常开发中容易忽略的问题,可能是最低级的编码常见问题,往往...

631
来自专栏java一日一条

Java面试参考指南(一)

Java是一种基于面向对象概念的编程语言,使用高度抽象化来解决现实世界的问题。 面向对象的方法将现实世界中的对象进行概念化,以便于在应用之间进行重用。例如...

1693
来自专栏开发技术

排序之堆排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

932
来自专栏数据结构与算法

3285 转圈游戏 2013年NOIP全国联赛提高组

3285 转圈游戏 2013年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2778
来自专栏攻城狮的动态

简谈快速排序

36910

扫码关注云+社区

领取腾讯云代金券