一、HashMap的概述
HashMap是一种基于哈希表的数据结构,它将键映射到值。实现HashMap需要使用hashCode和equals方法,hashCode用于计算键的哈希值,equals方法用于比较键的值是否相等。HashMap将键的哈希值映射到数组的下标,将键和值存储在数组中的相应位置。 HashMap允许null键和null值。HashMap不是同步的,因此在并发环境中的操作可能会引发线程安全问题。 下面是HashMap的代码示例:
public class HashMap
extends AbstractMap
implements Map
, Cloneable, Serializable {
/* HashMap的内部实现 */
}
二、HashMap的主要属性
HashMap的主要属性包括: - capacity:HashMap中的数组容量,默认值为16,必须是2的幂。 - loadFactor:HashMap的装载因子,默认值为0.75,用于确定何时需要调整HashMap的容量。 - threshold:HashMap的阈值,表示当Hash表中元素个数超过该值,需要进行扩容操作。 - modCount:用于实现迭代器的快速失败机制。 下面是HashMap的主要属性的代码示例:
public class HashMap
extends AbstractMap
implements Map
, Cloneable, Serializable {
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bin.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/* HashMap的内部实现 */
}
三、HashMap的哈希算法
HashMap使用哈希算法将键值对映射到数组的下标,HashMap使用的哈希算法是JDK官方提供的哈希算法,它将键的哈希值右移16位并且与原哈希值进行异或操作,然后将结果作为数组下标。 下面是HashMap的哈希算法的代码实例:
final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
四、HashMap的底层数据结构
HashMap的底层数据结构是一个数组和一个链表。数组的大小为2的n次方,链表用来解决哈希冲突。当多个键映射到数组的同一个下标时,HashMap会将这些键值对保存在同一个链表中。当链表长度达到8时,链表将被转换为红黑树,这样可以提高查找效率。 下面是HashMap的底层数据结构的代码示例:
static class Node
implements Map.Entry
{
final int hash;
final K key;
V value;
Node
next;
Node(int hash, K key, V value, Node
next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString(){ return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
五、HashMap的代码示例
下面是一个简单的HashMap的代码示例,用于将学生的姓名和成绩保存在HashMap中:
import java.util.HashMap;
public class TestHashMap {
public static void main(String[] args) {
HashMap<String, Integer> scores = new HashMap<>();
scores.put("张三", 90);
scores.put("李四", 80);
scores.put("王五", 70);
scores.put("赵六", 60);
for (String name : scores.keySet()) {
System.out.println(name + "的成绩为:" + scores.get(name));
}
}
}
输出结果为:
张三的成绩为:90
李四的成绩为:80
王五的成绩为:70
赵六的成绩为:60