首页 > 代码库 > 浅谈HashMap实现原理
浅谈HashMap实现原理
我们都知道数组和链表的优劣,那HashMap有效地整合了数组和链表,形成了新的一种数据装载模型。
利用数组+链表的优势
1、减少数组不必要空间的开辟(假如单纯利用数组实现装载,我们总要考虑预先分配一部分内存,总不能需要的时候才开辟吧?在设计理念上也不符),利用链表能够更好地实现动态分配内存(通过引用关系指定);
2、通过散列均匀地将下标一致的对象挂在相应的链表下,这样的好处是通过数组和链表的整合减少了查询的复杂度(遍历最大次数为 数组长度+某链表下长度)
3、总之一句话“悟天克斯的合体”
HashMap最基本的结构是由Entry 一个内部静态类定义的
static class Entry<K,V> implements Map.Entry<K,V> { final K key;//key V value;//value Entry<K,V> next;//链表结构,指定的下一个Entry int hash;//通过散列获取的唯一的hash值,在put环节将作为一部分条件来验证Entry是否重复 /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); } /** * This method is invoked whenever the value in an entry is * overwritten by an invocation of put(k,v) for a key k that‘s already * in the HashMap. */ void recordAccess(HashMap<K,V> m) { } /** * This method is invoked whenever the entry is * removed from the table. */ void recordRemoval(HashMap<K,V> m) { } }
以下是我们常用的put方法
public V put(K key, V value) { //是否需要初始化,区别在于put是否是第一次操作,如果是第一次操作将会初始化一个数组table出来 if (table == EMPTY_TABLE) { inflateTable(threshold); } //HashMap是可以put key为null的键值对的,此Entry将会放在table[0]所在的链表下,具体在链表的什么位置只能看他是什么时候put进去的了,毕竟链表结构是先来得先排前面 if (key == null) return putForNullKey(value); //通过散列获取hash int hash = hash(key); //通过hash和table长度确定所属链表 下标(分组) int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //关于HashMap put如何确定put的key重复 在此处做了逻辑判断 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //后续会有扩容操作 addEntry(hash, key, value, i); return null; }
有同学不解了,如何通过hash和长度确定所属的链表(所属的组,将链表看作一个组)
//通过hash和table长度确定所属链表 下标(分组)
int i = indexFor(hash, table.length);
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; //通过与运算 返回了一个 0至length-1之间的int数据 return h & (length-1); }
接下来就是找好队长去排队,如果没有队长那么我来担任队长
Entry<K,V> e = table[i]; e != null; e = e.next
待更!
浅谈HashMap实现原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。