首页 / JAVA / java7之HashMap详解
java7之HashMap详解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java7之HashMap详解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含16896字，纯文字阅读大概需要25分钟。
内容图文
源码剖析
1. HashMap（jdk1.7版本） - 此篇详解
大家都知道，jdk1.7版本底层数组+链表(单向链表)，结合笔者的经验之谈，我觉得在分析HashMap集合具体操作源码前，有必要先了解下其底层链表结构，上源码…
- 链表结构 - 单向链表
/**
* HashMap1.7中定义- 单向链表
*/
static class Entry<K,V> implements Map.Entry<K,V> {
// key值
final K key;
// value值
V value;
// 下一个节点
Entry<K,V> next;
// hash值
int hash;
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;
}
// 重写equals方法
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;
}
// 重写hashCode方法
public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); }
// 重写toString方法
public final String toString() { return getKey() + "=" + getValue(); }
// value被覆盖调用一次
void recordAccess(HashMap<K,V> m) { }
// todo：此此两方法主要作用于HashMap的子类实现，eg：linkedHashMap
// 每移除一个entry就被调用一次
void recordRemoval(HashMap<K,V> m) { }
}
每一个Entry节点包含四个属性：key表示当前节点key值；value表示当前节点value值，next节点表示当前节点下一个节点，如当前节点为链表末尾节点，则当前节点的next节点为null；hash表示当前节点key值通过算法计算出来的hash值；
单个Entry节点：
单向链表图解：
HashMap1.7版本底层 数组 + 单向链表 图解：
- 构造函数
// 数组默认初始容量 - 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 加载因子 - 默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 加载因子
final float loadFactor;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 扩容阈值(也表示hashMap底层数组实际存放元素大小)
int threshold;
/**
* 无参构造
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 有参构造
* @param initialCapacity：自定义初始容量
* @param loadFactor：自定义
*/
public HashMap(int initialCapacity, float loadFactor) {
// 判断初始容量值有效性
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
// 判断最大初始容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 判断加载因子有效性
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 设置加载因子-默认0.75
this.loadFactor = loadFactor;
// 设置扩容阈值(构造初始化为16，第一次put为12)
threshold = initialCapacity;
// 模板方法-默认无实现
init();
}
// 模板方法-设计模式：表示继承可拓展
void init() {
}
从源码中可以看出，构造只为相关参数（加载因子、扩容阈值）进行初始化；
其中需注意一点，我们都知道HashMap的扩容阈值为12，但在构造初始化的时候扩容阈值为16
- put() - 添加元素方法
// 数组默认值-空数组
static final Entry<?,?>[] EMPTY_TABLE = {};
// 底层数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// HashMap元素个数
transient int size;
// 记录对HashMap操作次数
transient int modCount;
transient int hashSeed = 0;
/**
* 入口
*/
public V put(K key, V value) {
// 1.第一次put元素
// 数组为空进行参数初始化-表示第一次put元素
if (table == EMPTY_TABLE) {
// 数组初始化/参数初始化
// 第一次put时，threshold经过构造方法赋值为16
inflateTable(threshold);
}
// 2.添加key为null的元素
if (key == null)
return putForNullKey(value);
// 3.添加key非null的元素
// 计算hash值
int hash = hash(key);
// 计算数组对应下标值
int i = indexFor(hash, table.length);
// 遍历数组下标为i的链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// hash冲突 && key相同
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 获取遍历节点元素值
V oldValue = e.value;
// 对value进行覆盖
e.value = value;
// value被覆盖时调用
e.recordAccess(this);
// 返回旧元素值
return oldValue;
}
}
// 操作次数++
modCount++;
// 添加Entry节点
addEntry(hash, key, value, i);
return null;
}
// 数组初始化/参数初始化
private void inflateTable(int toSize) {
// 计算初始容量
// 第一次put时，返回值：16
int capacity = roundUpToPowerOf2(toSize);
// 计算扩容阈值：16 * 0.75 = 12
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 初始化长度为16的table数组
table = new Entry[capacity];
// 此方法不影响主要功能
initHashSeedAsNeeded(capacity);
}
// 用于返回大于等于最接近number的2的整数次幂
private static int roundUpToPowerOf2(int number) {
// 第一次put元素时: 16 >= 数组最大容量(1 << 30) ? (1 << 30) : (16 > 1) ? Integer.highestOneBit((16-1) << 1) : 1
// Integer.highestOneBit((16-1) << 1) = Integer.highestOneBit(30) = 16
return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 添加key为null的元素 - 可以看出key为null时，存放在数组下标为0的位置
private V putForNullKey(V value) {
// 遍历数组下标为0的链表
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
// 获取遍历节点元素值
V oldValue = e.value;
// 对value进行覆盖
e.value = value;
// value被覆盖时调用
e.recordAccess(this);
// 返回旧值
return oldValue;
}
}
// 操作次数++
modCount++;
// 添加Entry节点
addEntry(0, null, value, 0);
return null;
}
// 添加Entry节点
void addEntry(int hash, K key, V value, int bucketIndex) {
// map元素个数 > 扩容阈值 && 当前数组位置对应链表不为空
if ((size >= threshold) && (null != table[bucketIndex])) {
// 将源数组中的元素值散列至新数组
resize(2 * table.length);
// 计算hash值 - 重新计算
hash = (null != key) ? hash(key) : 0;
// 计算对应新数组下标位置
bucketIndex = indexFor(hash, table.length);
}
// 添加Eentry节点
createEntry(hash, key, value, bucketIndex);
}
// 将源数组中的元素值散列至新数组
void resize(int newCapacity) {
// 获取源数组
Entry[] oldTable = table;
// 获取源数组长度
int oldCapacity = oldTable.length;
// 数组长度最大值设置
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建长度为源数组长度2倍的新数组
Entry[] newTable = new Entry[newCapacity];
// 将源数组中的元素值散列至新数组
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 将新数组赋值至源数组
table = newTable;
// 重新计算扩容阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 获取当前Key对应hash值
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String)
return sun.misc.Hashing.stringHash32((String) k);
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// 获取对应数组下标位置
static int indexFor(int h, int length) {
return h & (length-1);
}
// 添加Eentry节点
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取数组下标对应链表
Entry<K,V> e = table[bucketIndex];
// 向链表中添加节点
table[bucketIndex] = new Entry<>(hash, key, value, e);
// HashMap元素个数++
size++;
}
// 将源数组中元素散列至新数组中
void transfer(Entry[] newTable, boolean rehash) {
// 获取新数组长度
int newCapacity = newTable.length;
// 遍历源数组，将元素按照一定规则散列至新数组
// 外循环：遍历数组
for (Entry<K,V> e : table) {
// 内循环：遍历数组位置对应链表
while(null != e) {
// 获取当前节点下一个节点
Entry<K,V> next = e.next;
if (rehash) {
// true：重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
// 获取对应新数组的下标值
int i = indexFor(e.hash, newCapacity);
// 下面三步一定要连起来去思考：
// **前提条件，2次循环都作用于新数组同一下标位置的情况：
// 第一次循环时，newTable[i]为空，先赋值给当前遍历节点的下个节点，再将当前遍历节点赋值给对应新下标的新数组，最后继续循环
// 第二次循环时，newTable[i]为上次(存入同一下标位置对应新数组的链表)，然后赋值给当前遍历节点的下个节点(此节点实则为上一次遍历节点的下一个节点，
// 从这里可以看出，HashMap1.7这里用的是头插法)，再将此链表赋值给同一下标位置的新数组中，最后不为空继续循环；
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
put()添加元素方法只做了三件事，下面我们拆解分析下：
- 第一次put元素（当前为第一次添加元素时）：
- 计算扩容阈值：
<span style="color:#000000"><code class="language-java"> threshold <span style="color:#ac9739">=</span> <span style="color:#999999">(</span><span style="color:#6679cc">int</span><span style="color:#999999">)</span> Math<span style="color:#999999">.</span><span style="color:#3d8fd1">min</span><span style="color:#999999">(</span>capacity <span style="color:#ac9739">*</span> loadFactor<span style="color:#999999">,</span> MAXIMUM_CAPACITY <span style="color:#ac9739">+</span> <span style="color:#ac9739">1</span><span style="color:#999999">)</span><span style="color:#999999">;</span> <span style="color:#6b7394">// threshold = 16 * 0.75 = 12</span>
</code></span>- 初始化底层数组：
<span style="color:#000000"><code class="language-java"> table <span style="color:#ac9739">=</span> <span style="color:#6679cc">new</span> Entry<span style="color:#999999">[</span>capacity<span style="color:#999999">]</span><span style="color:#999999">;</span> <span style="color:#6b7394">// capacity = 16</span>
</code></span>- 添加key为null的元素：
遍历数组下标为0的链表：
⑴ 如判断已存在 key=null 的节点，则覆盖其value值；
if (e.key == null) {
// 获取遍历节点元素值
V oldValue = e.value;
// 对value进行覆盖
e.value = value;
// value被覆盖时调用
e.recordAccess(this);
// 返回旧值
return oldValue;
}
⑵ 反之，则添加节点；
// 操作次数++
modCount++;
// 添加Entry节点
addEntry(0, null, value, 0);
- 添加key非null的元素：
-
计算key键对应的hash值：
-
通过hash值计算对应数组下标存放位置；
-
遍历数组对应下标的链表(步骤2计算的下标)：
⑴ 如判断hash值相等且key值相等，则覆盖其value值；
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 获取遍历节点元素值
V oldValue = e.value;
// 对value进行覆盖
e.value = value;
// value被覆盖时调用
e.recordAccess(this);
// 返回旧元素值
return oldValue;
}
⑵ 反之，则添加节点；
// 操作次数++
modCount++;
// 添加Entry节点
addEntry(0, null, value, 0);
- get() - 获取元素方法
/**
* 入口
*/
public V get(Object key) {
// key为空时获取元素值
if (key == null)
return getForNullKey();
// 获取key对应Entry链表
Entry<K,V> entry = getEntry(key);
// 返回对应元素值
return null == entry ? null : entry.getValue();
}
// key为空获取元素值 - 可以看出key为null时，在下标为0的位置的数组获取
private V getForNullKey() {
// map元素个数为0时返回 null
if (size == 0) {
return null;
}
// 获取下标为0的链表
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 遍历key=null，返回对应元素值
if (e.key == null)
return e.value;
}
// 无->返回null
return null;
}
// 获取key对应Entry链表
final Entry<K,V> getEntry(Object key) {
// map元素个数为0时返回 null
if (size == 0) {
return null;
}
// 计算hash
int hash = (key == null) ? 0 : hash(key);
// 1.计算对应数组下标值 2.遍历数组位置对应链表
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
// hash相等 && key相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
// 无->返回null
return null;
}
从源码中可以看出，获取元素时做了2件事：
- 获取 key=null 的元素：
-
遍历数组下标为0的链表：
⑴ 如判断已存在 key=null 的节点，则返回其value值；
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
// 遍历key=null，返回对应元素值
if (e.key == null)
return e.value;
}
⑵ 反之，则返回null；
- 获取 key非null 的元素：
-
计算key键对应的hash值：
-
通过hash值计算对应数组下标存放位置；
-
遍历数组对应下标的链表(步骤2计算的下标)：
⑴ 如判断hash值相等且key值相等，则返回其value值；
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
// hash相等 && key相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
⑵ 反之，则返回 null；
- remove() - 删除元素方法
/**
* 入口
*/
public V remove(Object key) {
// 获取key对应Entry链表
Entry<K,V> e = removeEntryForKey(key);
// 返回删除元素值
return (e == null ? null : e.value);
}
// 获取删除元素对应Entry链表
final Entry<K,V> removeEntryForKey(Object key) {
// map元素个数为0时返回 null
if (size == 0) {
return null;
}
// 计算hash值
int hash = (key == null) ? 0 : hash(key);
// 计算对应数组下标位置
int i = indexFor(hash, table.length);
// 获取数组下标为i对应链表
Entry<K,V> prev = table[i];
// 链表第一次赋值
Entry<K,V> e = prev;
// 遍历此链表
while (e != null) {
// 获取当前节点下一个节点
Entry<K,V> next = e.next;
Object k;
// hash相等 && key相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
// 操作次数++
modCount++;
// map元素个数--
size--;
// 当前判断表示：循环此链表第一个节点
if (prev == e)
// 直接将当前遍历(删除)节点的下一个节点赋值即可
table[i] = next;
else
// 表示循环非此链表第一个节点
// 将上个节点的next节点设置为 当前遍历(删除)节点的下一个节点
prev.next = next;
// 移除一个entry调用一次
e.recordRemoval(this);
// 返回删除节点
return e;
}
// 将当前遍历(非删除)节点赋值给prev
prev = e;
// 将当前遍历(非删除)节点的下一个节点赋值给e(下一次遍历的节点)
e = next;
}
// e!=null但无对应key -> 返回此链表最后一个Entry节点
// e==null -> 返回null
return e;
}
删除元素实则就做了一件事，修改节点之间的引用；
- HashMap（jdk1.7版本）总结：
- 底层为数组 + 链表(单向链表)；
- 线程不安全；
- 数组初始容量为16；
- 扩容加载因子为0.75；
- 扩容阈值 a.构造之后为16，第一次put()方法后为12；
- 扩容死循环问题 - 笔者之后会另起一篇详解；
- 有modCount；
内容总结
以上是互联网集市为您收集整理的java7之HashMap详解全部内容，希望文章能够帮你解决java7之HashMap详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。