java源码研究-HashMap

来源:转载

HashMap的用法相信我不用解释了,常用于无序键值对的存放,由于其有良好的查找和插入性能,是大量使用的数据结构。HashMap相关的方法有get,put,常见的参数包括loadFactor,Capacity等,在后面都会提到。经常被提到的另两个相似的类是HashTable和java.util.concurrent.ConcurrentHashMap ,这三个类主要区别是多线程时候的性能以及是否线程安全,一言以蔽之:性能HashMap>ConcurrentHashMap>HashTable,但是HashMap是非线程安全的,其余则安全。

最近面试老被问到hashMap的实现,于是花了点时间对其完整的看了一遍。话不多说,进入正题。

基本的原理

java.util.HashMap中有一个Entry[] table ,数据都存放在这个里面。

Entry是HashMap中的一个静态内部类。用于实现一个链表结构,节点表示map中的一个值,从定义可以看出:   首先entry是用于实现链表的一个节点,有key,value用于存储自身节点数据,还有next用于下个节点的引用。 再看HashMap中的get方法: 我们可以得到这几个结论: get就是查找对应entry的过程,entry链被放在table数组这n个桶里 1.对nullkey做单独处理,其实就是放在table[0]中。 2.根据key的hash值,决定entry在哪个桶。 3.对桶内的entry链表进行遍历,当查找到时返回value。 4.找不到,返回null 
这里要插一个不相关的,要遍历hashmap必须通过hashmap.entrySet().iterator()来遍历,前者本身没有实现iterable一定要注意。entrySet就是保存entry的Set集合类 再次重申,hashmap没有实现collection 接口和iterable接口
 loadFactor 和 initCapacity  我们看HashMap的默认构造函数: //最大容量   static final int MAXIMUM_CAPACITY = 1 << 30;  //默认加载因子,加载因子是一个比例,当HashMap的数据大小>=容量*加载因子时,HashMap会将容量扩容   static final float DEFAULT_LOAD_FACTOR = 0.75f;   //阈值,当实际数据大小超过threshold时,HashMap会将容量扩容,threshold=容量*加载因子 int threshold;  //加载因子  final float loadFactor;  可以清楚地看到,默认我们是构造了一个初始容量为16,加载因子为0.75f的一个map。第一次扩容发生在什么时候呢?16*0.75=12 有趣的细节 容量总是2的倍数,为什么呢?为了寻址的快速。 寻址是通过 index & (table.length-1)实现的,其实就是一个取模,如果table.length 是2的倍数的话,table.length-1 总是 111111... 的结构,与运算可以方便的得到mod值。  为什么不用类的hashcode,而是要再做一次hash?避免最坏情况。 int hash = hash(key.hashcode()); ----参见上文的get方法 我们来看hash函数干了什么。 从注释上可以看出:这个函数以位移和异或的方式保证了hashcode不会有最坏情况出现(即大多数kv都分到了同一个桶)。在默认的加载因子下最坏不超过8的冲突。其实就是让分布更加的均化。 引用了StackOverflow上面的老外解释:

关于扩容 之前提到了当容量达到阈值后,HashMap会进行扩容。扩容时干了什么呢? 可以看到,做的事情包括: 1.重新申请空间存放table 2.transfer(把老数据移到新的table中),并将table指向到新的table(之后老table自动垃圾收集掉) 3.调整新的threshold值,以便下一次的resize能够在put方法中被激活  如果研究put方法可以看到: 在put中有这么一个判断       

1 if (size++ >= threshold) 2 resize(2 * table.length);
View Code

    size的解释是The number of key-value mappings contained in this map. 而threshold已经解释过了。也就是说put时会对元素数量进行检查,并视情况进行扩容。

分享给朋友:
您可能感兴趣的文章:
随机阅读: