【Java】JDK1.7 HashMap解析

• Z时代
• 2024-01-10
• 分类：技术分享

    static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}

V get(Object key); //获得指定key的值
V put(K key, V value);  //添加key-value对
void putAll(Map<? extends K, ? extends V> m);  //将指定Map中的key-value对复制到此Map中
V remove(Object key);  //删除该key-value
boolean containsKey(Object key); //判断是否存在该key的key-value对；是则返回true
boolean containsValue(Object value);  //判断是否存在该value的key-value对；是则返回true
Set<K> keySet();  //单独抽取key序列，将所有key生成一个Set
Collection<V> values();  //单独value序列，将所有value生成一个Collection
void clear(); // 清除HashMap中的所有key-value对
int size();  // 返回HashMap中所有key-value对的数量
boolean isEmpty(); // 判断HashMap是否为空,size == 0时表示为空 

public class HashMapTest {
public static void main(String[] args) {
/**
* 1. 声明1个 HashMap的对象
*/
Map<String, Integer> map = new HashMap<String, Integer>();
/**
* 2. 向HashMap添加数据（放入键-值对）
*/
map.put("Java", 1);
map.put("HashMap", 2);
map.put("List",3);
map.put("set",4);
/**
* 3. 获取 HashMap 的某个数据
*/
System.out.println("" + map.get("HashMap"));
/**
* 4. 遍历HashMap共有3种方法：分别针对Entry或key或value
* 步骤1：获得Entry或key或value的集合
* 步骤2：遍历，使用for循环或迭代器Iterator
*/
// 方法1：获得Entry的Set集合再遍历
// 获得Entry的Set集合
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
// 通过for循环遍历
for(Map.Entry<String, Integer> entry : entrySet){
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}
// 通过迭代器遍历
// 先获得Entry的Iterator，再循环遍历
Iterator iter1 = entrySet.iterator();
while (iter1.hasNext()) {
// 遍历时，需先获取entry，再分别获取key、value
Map.Entry entry = (Map.Entry) iter1.next();
System.out.print((String) entry.getKey());
System.out.println((Integer) entry.getValue());
}
// 方法2：获得key的Set集合再遍历
Set<String> keySet = map.keySet();
// 通过for循环
for(String key : keySet){
System.out.print(key);
System.out.println(map.get(key));
}
// 通过迭代器遍历
// 先获得key的Iterator，再循环遍历
Iterator iter2 = keySet.iterator();
String key = null;
while (iter2.hasNext()) {
// 遍历时，需先获取key，再获取value
key = (String)iter2.next();
System.out.print(key);
System.out.println(map.get(key));
}
// 方法3：获得value的集合再遍历
Collection valueSet = map.values();
// 获得values的Iterator，再循环遍历
Iterator iter3 = valueSet.iterator();
while (iter3.hasNext()) {
System.out.println(iter3.next());
}
}
}

//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//扩容阈值 = 容量 x 加载因子，当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表
int threshold
//存储数据的Entry类型数组，长度=2的幂
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE
//HashMap中存储的键值对的数量
transient int size

 //加载因子，容量可指定
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);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
//加载因子等于默认值，容量可指定
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默认构造函数，加载因子，容量等于默认值
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//可传入一个map的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}

    public V put(K key, V value) {
//1.若entry数组为空，则初始化数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//2.若key == null，则将该键-值 存放到entry数组中的第1个位置，即table[0]
if (key == null)
return putForNullKey(value);
//3.若 key ≠ null，则计算存放entry数组中的位置
//3.1根据键值key计算hash值
int hash = hash(key);
//3.2根据hash值 最终获得 key对应存放的entry数组中位置
int i = indexFor(hash, table.length);
4. 通过遍历以该数组元素为头结点的链表,判断该key值是否已存在
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
4.1 若该key已存在，则用新value替换旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//4.2 若该key不存在，则将key-value添加到entry数组中,这里采用头插法
addEntry(hash, key, value, i);
return null;
}

    void addEntry(int hash, K key, V value, int bucketIndex) {
// 若不足够，则进行扩容（2倍),重新计算Hash值、重新计算key在扩容后的entry数组下标
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//若容量足够，则创建1个新的数组元素Entry并放入到entry数组中
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倍容量）新建1个entry数组，newtable
Entry[] newTable = new Entry[newCapacity];
//将旧entry数组上的entry数据转移到newtable中，从而完成扩容
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//新数组table引用到HashMap的table属性上
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//旧entry数组上的entry数据转移到newtable中，从而完成扩容，按旧链表的正序遍历链表，在新链表的头部依次插入，
//即扩容前 = 1->2->3，扩容后 = 3->2->1，此时若（多线程）并发执行 `put（）操作，一旦出现扩容情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环Infinite Loop
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) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

    public V get(Object key) {
//当key == null时，则到以entry数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
if (key == null)
return getForNullKey();
//当key ≠ null时，去获得对应值
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 1. 根据key值，通过hash（）计算出对应的hash值
// 2. 根据hash值计算出对应的数组下标
// 3. 遍历以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

数据结构

JDK1.7的HashMap采用数组+单链表的数据结构，数组和链表存储的是一个个Entry对象

    static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}

常用方法

V get(Object key); //获得指定key的值
V put(K key, V value);  //添加key-value对
void putAll(Map<? extends K, ? extends V> m);  //将指定Map中的key-value对复制到此Map中
V remove(Object key);  //删除该key-value
boolean containsKey(Object key); //判断是否存在该key的key-value对；是则返回true
boolean containsValue(Object value);  //判断是否存在该value的key-value对；是则返回true
Set<K> keySet();  //单独抽取key序列，将所有key生成一个Set
Collection<V> values();  //单独value序列，将所有value生成一个Collection
void clear(); // 清除HashMap中的所有key-value对
int size();  // 返回HashMap中所有key-value对的数量
boolean isEmpty(); // 判断HashMap是否为空,size == 0时表示为空 

使用

public class HashMapTest {
public static void main(String[] args) {
/**
* 1. 声明1个 HashMap的对象
*/
Map<String, Integer> map = new HashMap<String, Integer>();
/**
* 2. 向HashMap添加数据（放入键-值对）
*/
map.put("Java", 1);
map.put("HashMap", 2);
map.put("List",3);
map.put("set",4);
/**
* 3. 获取 HashMap 的某个数据
*/
System.out.println("" + map.get("HashMap"));
/**
* 4. 遍历HashMap共有3种方法：分别针对Entry或key或value
* 步骤1：获得Entry或key或value的集合
* 步骤2：遍历，使用for循环或迭代器Iterator
*/
// 方法1：获得Entry的Set集合再遍历
// 获得Entry的Set集合
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
// 通过for循环遍历
for(Map.Entry<String, Integer> entry : entrySet){
System.out.print(entry.getKey());
System.out.println(entry.getValue());
}
// 通过迭代器遍历
// 先获得Entry的Iterator，再循环遍历
Iterator iter1 = entrySet.iterator();
while (iter1.hasNext()) {
// 遍历时，需先获取entry，再分别获取key、value
Map.Entry entry = (Map.Entry) iter1.next();
System.out.print((String) entry.getKey());
System.out.println((Integer) entry.getValue());
}
// 方法2：获得key的Set集合再遍历
Set<String> keySet = map.keySet();
// 通过for循环
for(String key : keySet){
System.out.print(key);
System.out.println(map.get(key));
}
// 通过迭代器遍历
// 先获得key的Iterator，再循环遍历
Iterator iter2 = keySet.iterator();
String key = null;
while (iter2.hasNext()) {
// 遍历时，需先获取key，再获取value
key = (String)iter2.next();
System.out.print(key);
System.out.println(map.get(key));
}
// 方法3：获得value的集合再遍历
Collection valueSet = map.values();
// 获得values的Iterator，再循环遍历
Iterator iter3 = valueSet.iterator();
while (iter3.hasNext()) {
System.out.println(iter3.next());
}
}
}

对于遍历方式，推荐使用针对 key-value对（Entry）的方式：效率高

1. 对于遍历keySet,valueSet，实质上遍历了2次：
   第1次，for/iterator迭代器遍历;
   第2次 从HashMap中取出key的value操作
2. 对于遍历entrySet，实质遍历了1次for/iterator迭代器遍历，Entry已经存储了key和 value

源码分析

主要属性

//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//扩容阈值 = 容量 x 加载因子，当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表
int threshold
//存储数据的Entry类型数组，长度=2的幂
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE
//HashMap中存储的键值对的数量
transient int size

构造方法

 //加载因子，容量可指定
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);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
//加载因子等于默认值，容量可指定
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//默认构造函数，加载因子，容量等于默认值
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//可传入一个map的构造函数
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}

put()方法

    public V put(K key, V value) {
//1.若entry数组为空，则初始化数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//2.若key == null，则将该键-值 存放到entry数组中的第1个位置，即table[0]
if (key == null)
return putForNullKey(value);
//3.若 key ≠ null，则计算存放entry数组中的位置
//3.1根据键值key计算hash值
int hash = hash(key);
//3.2根据hash值 最终获得 key对应存放的entry数组中位置
int i = indexFor(hash, table.length);
4. 通过遍历以该数组元素为头结点的链表,判断该key值是否已存在
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
4.1 若该key已存在，则用新value替换旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//4.2 若该key不存在，则将key-value添加到entry数组中,这里采用头插法
addEntry(hash, key, value, i);
return null;
}

addEntry resize() transfer()

    void addEntry(int hash, K key, V value, int bucketIndex) {
// 若不足够，则进行扩容（2倍),重新计算Hash值、重新计算key在扩容后的entry数组下标
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//若容量足够，则创建1个新的数组元素Entry并放入到entry数组中
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倍容量）新建1个entry数组，newtable
Entry[] newTable = new Entry[newCapacity];
//将旧entry数组上的entry数据转移到newtable中，从而完成扩容
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//新数组table引用到HashMap的table属性上
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//旧entry数组上的entry数据转移到newtable中，从而完成扩容，按旧链表的正序遍历链表，在新链表的头部依次插入，
//即扩容前 = 1->2->3，扩容后 = 3->2->1，此时若（多线程）并发执行 `put（）操作，一旦出现扩容情况，则容易出现环形链表，从而在获取数据、遍历链表时形成死循环Infinite Loop
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) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

get()方法

    public V get(Object key) {
//当key == null时，则到以entry数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
if (key == null)
return getForNullKey();
//当key ≠ null时，去获得对应值
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 1. 根据key值，通过hash（）计算出对应的hash值
// 2. 根据hash值计算出对应的数组下标
// 3. 遍历以该数组下标的数组元素为头结点的链表所有节点，寻找该key对应的值
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

源码总结

1.JDK1.7的HashMap采用数组+单链表的数据结构，数组和链表存储的是一个个Entry对象
2.添加key-value时会根据key值计算出对应的hash值，再根据hash值计算出对应的数组下标，遍历这个数组中的Entry链表，如果存在有相同的key的Entry,用新的value值替换旧的value值，若不存在则用头插法加入到链表中。
3.在添加key-value到数组中时有扩容的判断，但hashmap中Entry的数量，或者说key-value的数量大于扩容阈值 = 当前容量 x 加载因子，新建一个数组，容量时是数组的2倍，将旧entry数组上的entry数据转移到newtable中，让当前的数组指向新数组，从而完成扩容。
4.线程不安全问题：
在扩容过程中，在将旧数组上的数据转移到新数组上时，按旧链表的正序遍历链表，在新链表的采用头插法插入，即扩容前 = 1->2->3，扩容后 = 3->2->1，此时若（多线程）并发执行 `put（）操作，一旦出现扩容情况，则容易出现环形链表，从而在get()方法获取数据、遍历链表时形成死循环Infinite Loop

以上是 【Java】JDK1.7 HashMap解析 的全部内容， 来源链接： utcz.com/a/110833.html