HashMap 在我们的工作中应用的非常广泛,在工作面试中也经常会被问到,对于这样一个重要的集合模型我们有必要弄清楚它的使用方法和它底层的实现原理。HashMap 是通过 key-value 键值对的方式来存储数据的,通过 put、get 方法实现键值对的快速存取,这是 HashMap 最基本的用法。HashMap 底层是通过数组和链表相结合的混合结构来存放数据的。我们通过分析底层源码来详细了解一下 HashMap 的实现原理。
1、HashMap 的初始化
在 HashMap 实例化时我们要了解两个概念:初始容量和加载因子。HashMap 是基于哈希表的 Map 接口实现,初始容量是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超过了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍于当前容量的新的容量。
以上是 Java API 中 HashMap 的构造方法,其源码如下:
- 1 static final int DEFAULT_INITIAL_CAPACITY = 16;//默认初始容量16
- 2 static final int MAXIMUM_CAPACITY = 1 << 30;//定义最大容量
- 3 static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子0.75
- 4 transient Entry[] table;
- 5 int threshold; //临界值,值为容量与加载因子的乘积
- 6 final float loadFactor; //加载因子
- 7
- 8 public HashMap() {
- 9 this.loadFactor = DEFAULT_LOAD_FACTOR;
- 10 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
- 11 table = new Entry[DEFAULT_INITIAL_CAPACITY];
- 12 init();
- 13 }
- 14
- 15 void init() {
- 16 }
以上构造方法定义了一个空的 HashMap,其默认初始容量为 16,默认初始加载因子为 0.75,同时声明了一个 Entry 类型的数组,数组初始长度为 16。那么这里出现的 Entry 对象是如何定义的呢?看一下它的实现代码:
- 1 static class Entry implements Map.Entry {
- 2 final K key;
- 3 V value;
- 4 Entry next; //指向下一个Entry节点
- 5 final int hash; //哈希值
- 6 7
- /**
- 8 * Creates new entry.
- 9 */
- 10 Entry(int h, K k, V v, Entry n) {
- 11 value = v;
- 12 next = n;
- 13 key = k;
- 14 hash = h;
- 15
- }
- 16 17 public final K getKey() {
- 18
- return key;
- 19
- }
- 20 21 public final V getValue() {
- 22
- return value;
- 23
- }
- 24 25 public final V setValue(V newValue) {
- 26 V oldValue = value;
- 27 value = newValue;
- 28
- return oldValue;
- 29
- }
- 30 //重写equals方法,判断两个Entry是否相等,如果两个Entry对象的key和value相等,则返回true,否则返回false
- 31 public final boolean equals(Object o) {
- 32
- if (! (o instanceof Map.Entry)) 33
- return false;
- 34 Map.Entry e = (Map.Entry) o;
- 35 Object k1 = getKey();
- 36 Object k2 = e.getKey();
- 37
- if (k1 == k2 || (k1 != null && k1.equals(k2))) {
- 38 Object v1 = getValue();
- 39 Object v2 = e.getValue();
- 40
- if (v1 == v2 || (v1 != null && v1.equals(v2))) 41
- return true;
- 42
- }
- 43
- return false;
- 44
- }
- 45 //重写hashCode方法,返回key的hashCode值与value的hashCode值异或运算所得的值
- 46 public final int hashCode() {
- 47
- return (key == null ? 0 : key.hashCode()) ^ 48(value == null ? 0 : value.hashCode());
- 49
- }
- 50 //重写toString方法,返回此Entry对象的"key=value"映射关系
- 51 public final String toString() {
- 52
- return getKey() + "=" + getValue();
- 53
- }
- 54 55
- /**
- 56 * This method is invoked whenever the value in an entry is
- 57 * overwritten by an invocation of put(k,v) for a key k that's already
- 58 * in the HashMap.
- 59 */
- 60 void recordAccess(HashMap m) { //当向HashMap中添加键值对时,会调用此方法,这里方法体为空,即不做处理
- 61
- }
- 62 63
- /**
- 64 * This method is invoked whenever the entry is
- 65 * removed from the table.
- 66 */
- 67 void recordRemoval(HashMap m) { //当向HashMap中删除键值对映射关系时,会调用此方法,这里方法体为空,即不做处理
- 68
- }
- 69
- }
Entry 类是 HashMap 的内部类,其实现了 Map.Entry 接口。Entry 类里定义了 4 个属性:Object 类型的 key、value(K、V 类型可以看成 Object 类型),Entry 类型的 next 属性(这个 next 其实就是一个指向下一个 Entry 对象的引用,形成了一个链表,通过此 Entry 对象的 next 属性可以找到其下一个 Entry 对象)和 int 型的 hash 值。HashMap 底层维护的就是一个个 Entry 对象。在 Entry 类里还重写了 equals 方法,若两个 Entry 的 key 和 value 都相等,则返回 true,否则返回 false,同时还重写了 hashCode 方法。
2、HashMap 的底层数据结构
前面提到过 HashMap 的底层是基于数组和链表来实现的,那么如何决定一个 Entry 对象是存放在数组中的哪个位置的呢?它是通过计算 hash 值来决定存储位置的,同时在查找元素的时候同样也是计算出一个值来找到对应的位置,因此它具有相当快的查询速度。HashMap 是根据 key 的 hashCode 值来计算 hash 值的,相同的 hashCode 值计算出来的 hash 值也是相同的。当存储的对象达到了一定数量,就有可能出现不同对象的 key 的 hashCode 值是相同的,因此计算出来的 hash 值也相同,这样就出现了冲突。哈希冲突的解决方法有很多,比如再哈希法,这种方法是同时构造多个不同的哈希函数,当发生冲突时就换另外的函数重新计算 hash 值,直到不再产生冲突为止。HashMap 是通过单链表来解决哈希冲突的,这种方法也被称为拉链法。如图所示:
在上图中,左边的部分是哈希表(也称为哈希数组),右边是一个单链表,单链表是用来解决哈希冲突的,数组里的每一个元素都是一个单链表的头节点,当不同的 key 计算出的数组中的存放位置相同时,就将此对象添加到单链表中。
3、数据存储
在 HashMap 中定义了 put 方法来向集合中添加数据,数据以键值对的形式存储,put 方法的实现如下:
- 1 public V put(K key, V value) {
- 2 //如果存入HashMap的key为null,则将该键值对添加到table[0]中
- 3
- if (key == null) 4
- return putForNullKey(value);
- 5 //key不为null,调用hash方法计算key的hashCode值对应的hash值
- 6 int hash = hash(key.hashCode());
- 7 //根据计算出的hash值,结合数组的长度计算出数组中的插入位置i
- 8 int i = indexFor(hash, table.length);
- 9 //遍历数组下标为i处的链表,如果链表上存在元素,其hash值与上述计算得到的hash值相等,
- 10 //并且其key值与新增的键值对的key值相等,那么就以新增键值对的value替换此元素的value值,
- 11 //并返回此元素原来的value
- 12
- for (Entry e = table[i]; e != null; e = e.next) {
- 13 Object k;
- 14
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
- 15 V oldValue = e.value;
- 16 e.value = value;
- 17 e.recordAccess(this);
- 18
- return oldValue;
- 19
- }
- 20
- }
- 21 22 modCount++; //操作次数加1
- 23 //如果链表上不存在满足条件的元素,则将键值对对应生成的Entry对象添加到table[i]处,
- 24 //并将下标为i处原先的Entry对象链接到新的Entry对象后面
- 25 addEntry(hash, key, value, i);
- 26
- return null;
- 27
- }
- 28 29 30 31 private V putForNullKey(V value) {
- 32 //遍历数组下标为0处的链表,如果链表中存在元素其key为null,则用value覆盖此元素原来的value
- 33
- for (Entry e = table[0]; e != null; e = e.next) {
- 34
- if (e.key == null) {
- 35 V oldValue = e.value;
- 36 e.value = value;
- 37 e.recordAccess(this);
- 38
- return oldValue;
- 39
- }
- 40
- }
- 41 modCount++; //操作数加1
- 42 //如果链表中不存在满足条件的元素,则将此键值对生成的Entry对象存放到table[0]
- 43 addEntry(0, null, value, 0); //key为null,计算出的hash值为0
- 44
- return null;
- 45
- }
- 46 47 48 //计算hash值
- 49 static int hash(int h) {
- 50 // This function ensures that hashCodes that differ only by
- 51 // constant multiples at each bit position have a bounded
- 52 // number of collisions (approximately 8 at default load factor).
- 53 h ^= (h >>> 20) ^ (h >>> 12);
- 54
- return h ^ (h >>> 7) ^ (h >>> 4);
- 55
- }
- 56 57 58 59 //根据hash值和数组长度,计算出在数组中的索引位置
- 60 static int indexFor(int h, int length) {
- 61
- return h & (length - 1); //计算出的值不会超出数组的长度
- 62
- }
- 63 64 65 66 void addEntry(int hash, K key, V value, int bucketIndex) {
- 67 //获取table[bucketIndex]处的Entry对象
- 68 Entry e = table[bucketIndex];
- 69 //根据key-value生成新的Entry对象,并将新的Entry对象存入table[bucketIndex]处,将其next引用指向原来的对象
- 70 table[bucketIndex] = new Entry(hash, key, value, e);
- 71 //如果数组容量大于或等于临界值,则进行扩容
- 72
- if (size++>=threshold) 73 resize(2 * table.length); //容量为原来的2倍
- 74
- }
以上就是 put 方法的实现原理,我给出了详细的代码注释。上面已经讲到过 HashMap 底层的数据结构是由数组和单向链表构成的,当我们向 HashMap 中 put 一对 key-value 键值对时,首先判断 key 是否为 null,如果为 null,则遍历 table[0] 处的链表,若此链表上存在 key 为 null 的元素,则用 value 覆盖此元素的 value 值,如果不存在这样的元素,那么将此键值对生成的 Entry 对象存放到 table[0] 中;如果 key 不为 null,首先根据 key 的 hashCode 值计算出 hash 值,根据 hash 值和数组长度计算出要存放到数组中的位置 i,然后遍历 table[i] 处的链表,如果链表上存在元素其 hash 值与计算得到的 hash 值相等并且其 key 值与新增的 key 相等,那么就以新增的 value 覆盖此元素原来的 value 并返回原来的 value 值;如果链表上不存在满足上面条件的元素,则将 key-value 生成的 Entry 对象存放到 table[i] 处,并将其 next 指向此处原来的 Entry 对象。这样经过多次 put 操作,就构成了数组加链表的存储结构。
4、数据读取
HashMap 的 get 方法可以根据 key 返回其对应的 value,如果 key 为 null,则返回 null。
- 1 public V get(Object key) {
- 2 //如果key为null,则循环table[0]处的单链表
- 3
- if (key == null) 4
- return getForNullKey();
- 5 //key不为null,根据key的hashCode计算出一个hash值
- 6 int hash = hash(key.hashCode());
- 7 //根据hash值和数组长度计算出一个数组下标值,并且遍历此下标处的单链表
- 8
- for (Entry e = table[indexFor(hash, table.length)]; 9 e != null; 10 e = e.next) {
- 11 Object k;
- 12 //如果Entry对象的hash值跟上面计算得到的hash值相等,并且key也相等,那么就返回此Entry对象value
- 13
- if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 14
- return e.value;
- 15
- }
- 16 //如果单链表上不存在满足上述条件的Entry对象,则表明HashMap不包含该key的映射关系,返回null
- 17
- return null;
- 18
- }
- 19 20 21 22 private V getForNullKey() {
- 23 //获取table[0]处的Entry对象,并循环其链接的单链表,如果单链表上存在不为null的对象,
- 24 //并且其key为null,那么就返回此对象的value
- 25
- for (Entry e = table[0]; e != null; e = e.next) {
- 26
- if (e.key == null) 27
- return e.value;
- 28
- }
- 29 //如果单链表上不存在满足条件的对象,则返回null
- 30
- return null;
- 31
- }
了解了 put 方法的原理,我们就不难理解 get 的实现原理了,与之类似也是要根据 key 的 hashCode 值来计算出一个 hash 值,然后根据 hash 值和数组长度计算出一个数组下标值,接着循环遍历此下标处的单链表,寻找满足条件的 Entry 对象并返回 value,此 value 就是 HashMap 中该 key 所映射的 value。注意分析当 key 为 null 时的情况:如果 HashMap 中有 key 为 null 的映射关系,那么就返回 null 映射的 value,否则就表明 HashMap 中不存在 key 为 null 的映射关系,返回 null。同理,当 get 方法返回的值为 null 时,并不一定表明该映射不包含该键的映射关系,也可能是该映射将该键显示的映射为 null,即 put(key, null)。可使用 containKey 方法来区分这两种情况。
5、移除映射关系
remove 方法根据指定的 key 从 HashMap 映射中移除相应的映射关系(如果存在),此方法返回一个 value。
- 1 public V remove(Object key) {
- 2 Entry e = removeEntryForKey(key);
- 3
- return (e == null ? null: e.value);
- 4
- }
- 5 6 7 8 final Entry removeEntryForKey(Object key) {
- 9 //根据key的hashCode计算hash值
- 10 int hash = (key == null) ? 0 : hash(key.hashCode());
- 11 //根据hash值和数组长度计算数组下标值i
- 12 int i = indexFor(hash, table.length);
- 13 //获取下标为i处的数组元素
- 14 Entry prev = table[i];
- 15 Entry e = prev;
- 16 //遍历数组下标为i处的单链表
- 17
- while (e != null) {
- 18 Entry next = e.next;
- 19 Object k;
- 20 //如果此单链表上存在Entry对象e,其hash值与计算出的hash值相等并且其key也跟传入的key"相等",则从单链表上移除e
- 21
- if (e.hash == hash && 22((k = e.key) == key || (key != null && key.equals(k)))) {
- 23 modCount++;
- 24 size--; //map中的映射数减1
- 25 //判断满足条件的Entry对象是在数组下标i处还是在数组外面的单链表上
- 26
- if (prev == e) 27 table[i] = next;
- 28
- else 29 prev.next = next;
- 30 e.recordRemoval(this);
- 31
- return e;
- 32
- }
- 33 prev = e;
- 34 e = next;
- 35
- }
- 36 37
- return e;
- 38
- }
从上面的源码可以看出,remove 方法的原理是先找出满足条件的 Entry 对象,然后从单链表上删除该对象,并返回该对象中的 value,本质上是对单链表的操作。
6、总结
从以上源码的分析中我们知道了 HashMap 底层维护的是数组加链表的混合结构,这是 HashMap 的核心,只要掌握了这一点我们就能很容易弄清楚 HashMap 中映射关系的各种操作原理,其本质是对数组和链表的操作。要注意的是 HashMap 不是线程安全的,我们可以使用 Collections.synchoronizedMap 方法来获得线程安全的 HashMap。例如:
Map map = Collections.sychronizedMap(new HashMap());
以上是我个人对 HashMap 底层原理的一点理解,不妥的地方欢迎指正!
--- 恢复内容结束 ---
来源: http://www.cnblogs.com/fangfuhai/p/6420645.html