HashMap实现了Map接口,我们通过一个简单的例子来看如何使用。我们介绍过如何产生随机数,现在,我们写一个程序,来看随机产生的数是否均匀。比如,随机产生1000个0~3的数,统计每个数的次数,如代码所示。
Random rnd = new Random();
Map<Integer, Integer> countMap = new HashMap<>();
for(int i=0; i<1000; i++){
int num = rnd.nextInt(4);
Integer count = countMap.get(num);
if(count==null){
countMap.put(num, 1);
}else{
countMap.put(num, count+1);
}
}
for(Map.Entry<Integer, Integer> kv : countMap.entrySet()){
System.out.println(kv.getKey()+", "+kv.getValue());
}
一次运行的输出为:
除了默认构造方法, HashMap还有如下构造方法:
public HashMap(int initialCapacity)
public HashMap(int initialCapacity, float loadFactor)
public HashMap(Map<? extends K, ? extends V> m)
最后一个以一个已有的Map构造,复制其中的所有键值对到当前Map。前两个涉及参数initialCapacity和loadFactor,它们是什么意思呢?我们需要看下HashMap的实现原理。
实现原理
我们先来看HashMap的内部组成,然后分析一些主要方法的实现,代码基于Java 7。
1.内部组成
HashMap内部有如下几个主要的实例变量:
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
transient int size;
int threshold;
final float loadFactor;
size表示实际键值对的个数。table是一个Entry类型的数组,称为哈希表或哈希桶,其中的每个元素指向一个单向链表,链表中的每个节点表示一个键值对。Entry是一个内部类,它的实例变量和构造方法代码如下:
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
}
其中,key和value分别表示键和值,next指向下一个Entry节点,hash是key的hash值,待会我们会介绍其计算方法。直接存储hash值是为了在比较的时候加快计算,待会我们看代码。
table的初始值为EMPTY_TABLE,是一个空表,具体定义为:
static final Entry<? , ? >[] EMPTY_TABLE = {};
当添加键值对后,table就不是空表了,它会随着键值对的添加进行扩展,扩展的策略类似于ArrayList。添加第一个元素时,默认分配的大小为16,不过,并不是size大于16时再进行扩展,下次什么时候扩展与threshold有关。
threshold表示阈值,当键值对个数size大于等于threshold时考虑进行扩展。threshold是怎么算出来的呢?一般而言,threshold等于table.length乘以loadFactor。比如,如果table. length为16, loadFactor为0.75,则threshold为12。loadFactor是负载因子,表示整体上table被占用的程度,是一个浮点数,默认为0.75,可以通过构造方法进行修改。
2.默认构造方法
默认构造方法的代码为:
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
DEFAULT_INITIAL_CAPACITY为16, DEFAULT_LOAD_FACTOR为0.75,默认构造方法调用的构造方法主要代码为:
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
threshold = initialCapacity;
}
主要就是设置loadFactor和threshold的初始值。
3.保存键值对
下面,我们来看HashMap是如何把一个键值对保存起来的,代码为:
public V put(K key, V value) {
if(table == EMPTY_TABLE) {
inflateTable(threshold);
}
if(key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for(Entry<K, V> e = table[i]; e ! = null; e = e.next) {
Object k;
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;
}
如果是第一次保存,首先调用inflateTable()
方法给table分配实际的空间,inflateTable的主要代码为:
private void inflateTable(int toSize) {
//Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
}
默认情况下,capacity的值为16, threshold会变为12, table会分配一个长度为16的Entry数组。接下来,检查key是否为null,如果是,调用putForNullKey单独处理,我们暂时忽略这种情况。在key不为null的情况下,下一步调用hash方法计算key的hash值。hash方法的代码为:
final int hash(Object k) {
int h = 0
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
基于key自身的hashCode方法的返回值又进行了一些位运算,目的是为了随机和均匀性。有了hash值之后,调用indexFor方法,计算应该将这个键值对放到table的哪个位置,代码为:
static int indexFor(int h, int length) {
return h & (length-1);
}
HashMap中,length为2的幂次方,h&(length-1)
等同于求模运算h%length
。找到了保存位置i, table[i]
指向一个单向链表。接下来,就是在这个链表中逐个查找是否已经有这个键了,遍历代码为:
for (Entry<K, V> e = table[i]; e ! = null; e = e.next)
而比较的时候,是先比较hash值,hash相同的时候,再使用equals方法进行比较,代码为:
if(e.hash == hash && ((k = e.key) == key || key.equals(k)))
为什么要先比较hash呢?因为hash是整数,比较的性能一般要比equals高很多,hash不同,就没有必要调用equals方法了,这样整体上可以提高比较性能。如果能找到,直接修改Entry中的value即可。modCount++
的含义与ArrayList和LinkedList中介绍一样,为记录修改次数,方便在迭代中检测结构性变化。如果没找到,则调用addEntry方法在给定的位置添加一条,代码为:
void addEntry(int hash, K key, V value, int bucketIndex) {
if((size >= threshold) && (null ! = table[bucketIndex])) {
resize(2 * table.length);
hash = (null ! = key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
如果空间是够的,不需要resize,则调用createEntry方法添加。createEntry的代码为:
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K, V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
代码比较直接,新建一个Entry对象,插入单向链表的头部,并增加size。如果空间不够,即size已经要超过阈值threshold了,并且对应的table位置已经插入过对象了,具体检查代码为:
if((size >= threshold) && (null ! = table[bucketIndex]))
则调用resize方法对table进行扩展,扩展策略是乘2, resize的主要代码为:
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
分配一个容量为原来两倍的Entry数组,调用transfer方法将原来的键值对移植过来,然后更新内部的table变量,以及threshold的值。transfer方法的代码为:
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;
}
}
}
参数rehash一般为false。这段代码遍历原来的每个键值对,计算新位置,并保存到新位置,具体代码比较直接,就不解释了。
以上就是保存键值对的主要代码,简单总结一下,基本步骤为:
1)计算键的哈希值;
2)根据哈希值得到保存位置(取模);
3)插到对应位置的链表头部或更新已有值;
4)根据需要扩展table大小。
以上描述可能比较抽象,我们通过一个例子,用图示的方式进行说明,代码如下:
Map<String, Integer> countMap = new HashMap<>();
countMap.put("hello", 1);
countMap.put("world", 3);
countMap.put("position", 4);
在通过new HashMap()创建一个对象后,内存中的结构如图所示。
接下来执行保存键值对的代码,”hello”的hash值为96207088,模16的结果为0,所以插入table[0]
指向的链表头部,内存结构变为图所示。
“world”的hash值为111207038,模16结果为14,所以保存完”world”后,内存结构如图所示。
“position”的hash值为771782464,模16结果也为0, table[0]
已经有节点了,新节点会插到链表头部,内存结构变为如图所示。理解了键值对在内存是如何存放的,就比较容易理解其他方法了。
4.查找方法
根据键获取值的get方法的代码为:
public V get(Object key) {
if(key == null)
return getForNullKey();
Entry<K, V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
HashMap支持key为null, key为null的时候,放在table[0]
,调用getForNullKey()获取值;如果key不为null,则调用getEntry()获取键值对节点entry,然后调用节点的getValue()方法获取值。getEntry方法的代码是:
final Entry<K, V> getEntry(Object key) {
if(size == 0) {
return null;
}
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)计算键的hash值,代码为:
int hash = (key == null) ? 0 : hash(key);
2)根据hash找到table中的对应链表,代码为:
table[indexFor(hash, table.length)];
3)在链表中遍历查找,遍历代码:
for(Entry<K, V> e = table[indexFor(hash, table.length)];
e ! = null; e = e.next)
4)逐个比较,先通过hash快速比较,hash相同再通过equals比较,代码为:
if(e.hash == hash &&
((k = e.key) == key || (key ! = null && key.equals(k))))
containsKey方法的逻辑与get是类似的,节点不为null就表示存在,具体代码为:
public boolean containsKey(Object key) {
return getEntry(key) ! = null;
}
HashMap可以方便高效地按照键进行操作,但如果要根据值进行操作,则需要遍历, containsValue方法的代码为:
public boolean containsValue(Object value) {
if(value == null)
return containsNullValue();
Entry[] tab = table;
for(int i = 0; i < tab.length ; i++)
for(Entry e = tab[i] ; e ! = null ; e = e.next)
if(value.equals(e.value))
return true;
return false;
}
如果要查找的值为null,则调用containsNullValue单独处理;如果要查找的值不为null,遍历的逻辑也很简单,就是从table的第一个链表开始,从上到下,从左到右逐个节点进行访问,通过equals方法比较值,直到找到为止。
5.根据键删除键值对
根据键删除键值对的代码为:
public V remove(Object key) {
Entry<K, V> e = removeEntryForKey(key);
return(e == null ? null : e.value);
}
removeEntryForKey的代码为:
final Entry<K, V> removeEntryForKey(Object key) {
if(size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while(e ! = null) {
Entry<K, V> next = e.next;
Object k;
if(e.hash == hash &&
((k = e.key) == key || (key ! = null && key.equals(k)))) {
modCount++;
size--;
if(prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
基本逻辑分析如下。
1)计算hash,根据hash找到对应的table索引,代码为:
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
2)遍历table[i],查找待删节点,使用变量prev指向前一个节点,next指向后一个节点,e指向当前节点,遍历结构代码为:
Entry<K, V> prev = table[i];
Entry<K, V> e = prev;
while(e ! = null) {
Entry<K, V> next = e.next;
if(找到了){
//删除
return;
}
prev = e;
e = next;
}
3)判断是否找到,依然是先比较hash值,hash值相同时再用equals方法比较。
4)删除的逻辑就是让长度减小,然后让待删节点的前后节点链起来,如果待删节点是第一个节点,则让table[i]
直接指向后一个节点,代码为:
size--;
if(prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);在HashMap中代码为空,主要是为了HashMap的子类扩展使用。
6.总结
以上就是HashMap的基本实现原理,内部有一个哈希表,即数组table,每个元素table[i]
指向一个单向链表,根据键存取值,用键算出hash值,取模得到数组中的索引位置buketIndex,然后操作table[buketIndex]
指向的单向链表。
存取的时候依据键的hash值,只在对应的链表中操作,不会访问别的链表,在对应链表操作时也是先比较hash值,如果相同再用equals方法比较。这就要求,相同的对象其hashCode返回值必须相同,如果键是自定义的类,就特别需要注意这一点。这也是hash-Code和equals方法的一个关键约束。
需要说明的是,Java 8对HashMap的实现进行了优化,在哈希冲突比较严重的情况下,即大量元素映射到同一个链表的情况下(具体是至少8个元素,且总的键值对个数至少是64), Java 8会将该链表转换为一个平衡的排序二叉树,以提高查询的效率。
酷客教程相关文章:
评论前必须登录!
注册