Java中HashMap使用非常频繁的数据结构,其源码实现也有很多值得学习参考的地方。这里总结下我的学习,源码基于Jdk1.7,Java8中HashMap有很大的优化改进,再折腾学习。
基本思想
HashMap本身就是一个散列表(也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。HashMap存储的是Key-Value对,通过计算关于Key的函数,将要查询的Value映射到表中的一个记录访问,这样可以大大加快查找速度。其中映射函数称为散列函数(Hash函数),存放记录的数组称为散列表。当产生冲突时,HashMap将散列到同一个存储位置的所有元素保存在一个链表中。所以HashMap基本数据结构就是数组+链表实现的。
还有就是散列表(HashMap)中的容量(Capacity)和负载因子(Loadfactor)两个参数的理解。容量就是数组的大小,负载因子表示数组的填满程度,当数组中的元素(entry)数目大于Capacity*LoadFactor时候,就要对数组扩容,HashMap中默认会扩大两倍。HashMap默认的Capacity初始值为16,LoadFactor默认初始值为0.75。
HashMap中的数据结构
Entry对象
HashMap中的Entry定义:
Entry对象为HashMap中的内部类,实现了Map.Entry接口。Entry对象其实就是链表节点,一个Key-Value对用一个Entry对象表示。其中key、value存储的自然是键和值,next保存了下一个Entry对象的引用,hash为key对应的Hash值。
HashIterator
HashIterator是HahMap中迭代器的基本实现,然后ValueIterator、KeyIterator、EntryIterator都继承了HashIterator并重写了next()方法,实现了Key、Value和Entry的Iterator访问。理解了HashMap的原理后HashIterator也很容易理解了。首先在HashIterator的构造函数中将index移动到散列表中第一个不为空的bucket,比较重要的方法是nextEntry()方法,其实也就是在bucket上的链表和bucket之间移动。
看了HashIterator实现后我们也就理解了HashMap不能按元素的插入顺序来访问了,但JDK中提供了LinkedHashMap来保存元素的插入顺序,其实就是在HashMap的基础上实现了一个循环双向链表。
HashMap中的重要函数实现
get函数实现
|
|
put函数实现
put函数会根据key的hash函数值找到对应bucket的下标,若对应的bucket不为空,即发生了冲突,此时需要遍历bucket对应的Entry链表查看要插入的Key是否已经存在,若存在则替换原先的Value,不存在则在该bucket对应的链表头新插入一个Entry节点。若对应的bucket为空,则直接新建Entry存入对应bucket。
hash函数实现
|
|
总结
HashMap与HashTable
HashTable是早期JDK版本中的数据结构,现在已经基本不再使用了,HashMap与HasTable原理基本相同。主要区别除了HashMap在性能上的改进之外,还体现在:
1、HashMap支持key和Value为null,而HashTable中不支持;
2、HashTable是线程安全的,而HashMap非线程安全;
HashMap工作原理
HashMap是基于散列表的实现,结合了数组和链表的优点。HashMap中通过put和get存储和获取对象。存储对象时,我们将Key-Value传给put方法,它调用hashCode计算hash值从而得到bucket位置,进一步存储,在put方法中HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍);如果存储对象发生碰撞的时候,Hashmap通过链表将产生碰撞冲突的元素组织起来,在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。。获取对象时,我们将Key传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。