Java 中的HashMap详解和使用示例_动力节点Java学院整理
第1部分 hashmap介绍
hashmap简介
hashmap 是一个散列表,它存储的内容是键值对(key-value)映射。
hashmap 继承于abstractmap,实现了map、cloneable、java.io.serializable接口。
hashmap 的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,hashmap中的映射不是有序的。
hashmap 的实例有两个参数影响其性能:“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量,初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。通常,默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销,但同时也增加了查询成本(在大多数 hashmap 类的操作中,包括 get 和 put 操作,都反映了这一点)。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子,则不会发生 rehash 操作。
hashmap的构造函数
hashmap共有4个构造函数,如下:
// 默认构造函数。 hashmap() // 指定“容量大小”的构造函数 hashmap(int capacity) // 指定“容量大小”和“加载因子”的构造函数 hashmap(int capacity, float loadfactor) // 包含“子map”的构造函数 hashmap(map<? extends k, ? extends v> map)
hashmap的api
void clear() object clone() boolean containskey(object key) boolean containsvalue(object value) set<entry<k, v>> entryset() v get(object key) boolean isempty() set<k> keyset() v put(k key, v value) void putall(map<? extends k, ? extends v> map) v remove(object key) int size() collection<v> values()
第2部分 hashmap数据结构
hashmap的继承关系
java.lang.object java.util.abstractmap<k, v> java.util.hashmap<k, v> public class hashmap<k,v> extends abstractmap<k,v> implements map<k,v>, cloneable, serializable { }
hashmap与map关系如下图:
从图中可以看出:
(01) hashmap继承于abstractmap类,实现了map接口。map是"key-value键值对"接口,abstractmap实现了"键值对"的通用函数接口。
(02) hashmap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量:table, size, threshold, loadfactor, modcount。
table是一个entry[]数组类型,而entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在entry数组中的。
size是hashmap的大小,它是hashmap保存的键值对的数量。
threshold是hashmap的阈值,用于判断是否需要调整hashmap的容量。threshold的值="容量*加载因子",当hashmap中存储数据的数量达到threshold时,就需要将hashmap的容量加倍。
loadfactor就是加载因子。
modcount是用来实现fail-fast机制的。
第3部分 hashmap源码解析(基于jdk1.6.0_45)
为了更了解hashmap的原理,下面对hashmap源码代码作出分析。
在阅读源码时,建议参考后面的说明来建立对hashmap的整体认识,这样更容易理解hashmap。
package java.util; import java.io.*; public class hashmap<k,v> extends abstractmap<k,v> implements map<k,v>, cloneable, serializable { // 默认的初始容量是16,必须是2的幂。 static final int default_initial_capacity = 16; // 最大容量(必须是2的幂且小于2的30次方,传入容量过大将被这个值替换) static final int maximum_capacity = 1 << 30; // 默认加载因子 static final float default_load_factor = 0.75f; // 存储数据的entry数组,长度是2的幂。 // hashmap是采用拉链法实现的,每一个entry本质上是一个单向链表 transient entry[] table; // hashmap的大小,它是hashmap保存的键值对的数量 transient int size; // hashmap的阈值,用于判断是否需要调整hashmap的容量(threshold = 容量*加载因子) int threshold; // 加载因子实际大小 final float loadfactor; // hashmap被改变的次数 transient volatile int modcount; // 指定“容量大小”和“加载因子”的构造函数 public hashmap(int initialcapacity, float loadfactor) { if (initialcapacity < 0) throw new illegalargumentexception("illegal initial capacity: " + initialcapacity); // hashmap的最大容量只能是maximum_capacity if (initialcapacity > maximum_capacity) initialcapacity = maximum_capacity; if (loadfactor <= 0 || float.isnan(loadfactor)) throw new illegalargumentexception("illegal load factor: " + loadfactor); // 找出“大于initialcapacity”的最小的2的幂 int capacity = 1; while (capacity < initialcapacity) capacity <<= 1; // 设置“加载因子” this.loadfactor = loadfactor; // 设置“hashmap阈值”,当hashmap中存储数据的数量达到threshold时,就需要将hashmap的容量加倍。 threshold = (int)(capacity * loadfactor); // 创建entry数组,用来保存数据 table = new entry[capacity]; init(); } // 指定“容量大小”的构造函数 public hashmap(int initialcapacity) { this(initialcapacity, default_load_factor); } // 默认构造函数。 public hashmap() { // 设置“加载因子” this.loadfactor = default_load_factor; // 设置“hashmap阈值”,当hashmap中存储数据的数量达到threshold时,就需要将hashmap的容量加倍。 threshold = (int)(default_initial_capacity * default_load_factor); // 创建entry数组,用来保存数据 table = new entry[default_initial_capacity]; init(); } // 包含“子map”的构造函数 public hashmap(map<? extends k, ? extends v> m) { this(math.max((int) (m.size() / default_load_factor) + , default_initial_capacity), default_load_factor); // 将m中的全部元素逐个添加到hashmap中 putallforcreate(m); } static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> ) ^ (h >>> ); } // 返回索引值 // h & (length-)保证返回值的小于length static int indexfor(int h, int length) { return h & (length-); } public int size() { return size; } public boolean isempty() { return size == 0; } // 获取key对应的value public v get(object key) { if (key == null) return getfornullkey(); // 获取key的hash值 int hash = hash(key.hashcode()); // 在“该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.equals(k))) return e.value; } return null; } // 获取“key为null”的元素的值 // hashmap将“key为null”的元素存储在table[]位置! private v getfornullkey() { for (entry<k,v> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; } // hashmap是否包含key public boolean containskey(object key) { return getentry(key) != null; } // 返回“键为key”的键值对 final entry<k,v> getentry(object key) { // 获取哈希值 // hashmap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值 int hash = (key == null) ? 0 : hash(key.hashcode()); // 在“该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; } // 将“key-value”添加到hashmap中 public v put(k key, v value) { // 若“key为null”,则将该键值对添加到table[]中。 if (key == null) return putfornullkey(value); // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 int hash = hash(key.hashcode()); int i = indexfor(hash, table.length); for (entry<k,v> e = table[i]; e != null; e = e.next) { object k; // 若“该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; } } // 若“该key”对应的键值对不存在,则将“key-value”添加到table中 modcount++; addentry(hash, key, value, i); return null; } // putfornullkey()的作用是将“key为null”键值对添加到table[]位置 private v putfornullkey(v value) { for (entry<k,v> e = table[]; e != null; e = e.next) { if (e.key == null) { v oldvalue = e.value; e.value = value; e.recordaccess(this); return oldvalue; } } // 这里的完全不会被执行到! modcount++; addentry(0, null, value, 0); return null; } // 创建hashmap对应的“添加方法”, // 它和put()不同。putforcreate()是内部方法,它被构造函数等调用,用来创建hashmap // 而put()是对外提供的往hashmap中添加元素的方法。 private void putforcreate(k key, v value) { int hash = (key == null) ? 0 : hash(key.hashcode()); int i = indexfor(hash, table.length); // 若该hashmap表中存在“键值等于key”的元素,则替换该元素的value值 for (entry<k,v> e = table[i]; e != null; e = e.next) { object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } // 若该hashmap表中不存在“键值等于key”的元素,则将该key-value添加到hashmap中 createentry(hash, key, value, i); } // 将“m”中的全部元素都添加到hashmap中。 // 该方法被内部的构造hashmap的方法所调用。 private void putallforcreate(map<? extends k, ? extends v> m) { // 利用迭代器将元素逐个添加到hashmap中 for (iterator<? extends map.entry<? extends k, ? extends v>> i = m.entryset().iterator(); i.hasnext(); ) { map.entry<? extends k, ? extends v> e = i.next(); putforcreate(e.getkey(), e.getvalue()); } } // 重新调整hashmap的大小,newcapacity是调整后的单位 void resize(int newcapacity) { entry[] oldtable = table; int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) { threshold = integer.max_value; return; } // 新建一个hashmap,将“旧hashmap”的全部元素添加到“新hashmap”中, // 然后,将“新hashmap”赋值给“旧hashmap”。 entry[] newtable = new entry[newcapacity]; transfer(newtable); table = newtable; threshold = (int)(newcapacity * loadfactor); } // 将hashmap中的全部元素都添加到newtable中 void transfer(entry[] newtable) { entry[] src = table; int newcapacity = newtable.length; for (int j = ; j < src.length; j++) { entry<k,v> e = src[j]; if (e != null) { src[j] = null; do { entry<k,v> next = e.next; int i = indexfor(e.hash, newcapacity); e.next = newtable[i]; newtable[i] = e; e = next; } while (e != null); } } } // 将"m"的全部元素都添加到hashmap中 public void putall(map<? extends k, ? extends v> m) { // 有效性判断 int numkeystobeadded = m.size(); if (numkeystobeadded == 0) return; // 计算容量是否足够, // 若“当前实际容量 < 需要的容量”,则将容量x。 if (numkeystobeadded > threshold) { int targetcapacity = (int)(numkeystobeadded / loadfactor + ); if (targetcapacity > maximum_capacity) targetcapacity = maximum_capacity; int newcapacity = table.length; while (newcapacity < targetcapacity) newcapacity <<= ; if (newcapacity > table.length) resize(newcapacity); } // 通过迭代器,将“m”中的元素逐个添加到hashmap中。 for (iterator<? extends map.entry<? extends k, ? extends v>> i = m.entryset().iterator(); i.hasnext(); ) { map.entry<? extends k, ? extends v> e = i.next(); put(e.getkey(), e.getvalue()); } } // 删除“键为key”元素 public v remove(object key) { entry<k,v> e = removeentryforkey(key); return (e == null ? null : e.value); } // 删除“键为key”的元素 final entry<k,v> removeentryforkey(object key) { // 获取哈希值。若key为null,则哈希值为;否则调用hash()进行计算 int hash = (key == null) ? : hash(key.hashcode()); int i = indexfor(hash, table.length); entry<k,v> prev = table[i]; entry<k,v> e = prev; // 删除链表中“键为key”的元素 // 本质是“删除单向链表中的节点” 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; } // 删除“键值对” final entry<k,v> removemapping(object o) { if (!(o instanceof map.entry)) return null; map.entry<k,v> entry = (map.entry<k,v>) o; object key = entry.getkey(); int hash = (key == null) ? : hash(key.hashcode()); int i = indexfor(hash, table.length); entry<k,v> prev = table[i]; entry<k,v> e = prev; // 删除链表中的“键值对e” // 本质是“删除单向链表中的节点” while (e != null) { entry<k,v> next = e.next; if (e.hash == hash && e.equals(entry)) { modcount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordremoval(this); return e; } prev = e; e = next; } return e; } // 清空hashmap,将所有的元素设为null public void clear() { modcount++; entry[] tab = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; } // 是否包含“值为value”的元素 public boolean containsvalue(object value) { // 若“value为null”,则调用containsnullvalue()查找 if (value == null) return containsnullvalue(); // 若“value不为null”,则查找hashmap中是否有值为value的节点。 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值 private boolean containsnullvalue() { entry[] tab = table; for (int i = ; i < tab.length ; i++) for (entry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; } // 克隆一个hashmap,并返回object对象 public object clone() { hashmap<k,v> result = null; try { result = (hashmap<k,v>)super.clone(); } catch (clonenotsupportedexception e) { // assert false; } result.table = new entry[table.length]; result.entryset = null; result.modcount = 0; result.size = 0; result.init(); // 调用putallforcreate()将全部元素添加到hashmap中 result.putallforcreate(this); return result; } // entry是单向链表。 // 它是 “hashmap链式存储法”对应的链表。 // 它实现了map.entry 接口,即实现getkey(), getvalue(), setvalue(v value), equals(object o), hashcode()这些函数 static class entry<k,v> implements map.entry<k,v> { final k key; v value; // 指向下一个节点 entry<k,v> next; final int hash; // 构造函数。 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 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; } // 判断两个entry是否相等 // 若两个entry的“key”和“value”都相等,则返回true。 // 否则,返回false 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 (key==null ? 0 : key.hashcode()) ^ (value==null ? 0 : value.hashcode()); } public final string tostring() { return getkey() + "=" + getvalue(); } // 当向hashmap中添加元素时,绘调用recordaccess()。 // 这里不做任何处理 void recordaccess(hashmap<k,v> m) { } // 当从hashmap中删除元素时,绘调用recordremoval()。 // 这里不做任何处理 void recordremoval(hashmap<k,v> m) { } } // 新增entry。将“key-value”插入指定位置,bucketindex是位置索引。 void addentry(int hash, k key, v value, int bucketindex) { // 保存“bucketindex”位置的值到“e”中 entry<k,v> e = table[bucketindex]; // 设置“bucketindex”位置的元素为“新entry”, // 设置“e”为“新entry的下一个节点” table[bucketindex] = new entry<k,v>(hash, key, value, e); // 若hashmap的实际大小 不小于 “阈值”,则调整hashmap的大小 if (size++ >= threshold) resize( * table.length); } // 创建entry。将“key-value”插入指定位置,bucketindex是位置索引。 // 它和addentry的区别是: // () addentry()一般用在 新增entry可能导致“hashmap的实际容量”超过“阈值”的情况下。 // 例如,我们新建一个hashmap,然后不断通过put()向hashmap中添加元素; // put()是通过addentry()新增entry的。 // 在这种情况下,我们不知道何时“hashmap的实际容量”会超过“阈值”; // 因此,需要调用addentry() // () createentry() 一般用在 新增entry不会导致“hashmap的实际容量”超过“阈值”的情况下。 // 例如,我们调用hashmap“带有map”的构造函数,它绘将map的全部元素添加到hashmap中; // 但在添加之前,我们已经计算好“hashmap的容量和阈值”。也就是,可以确定“即使将map中 // 的全部元素添加到hashmap中,都不会超过hashmap的阈值”。 // 此时,调用createentry()即可。 void createentry(int hash, k key, v value, int bucketindex) { // 保存“bucketindex”位置的值到“e”中 entry<k,v> e = table[bucketindex]; // 设置“bucketindex”位置的元素为“新entry”, // 设置“e”为“新entry的下一个节点” table[bucketindex] = new entry<k,v>(hash, key, value, e); size++; } // hashiterator是hashmap迭代器的抽象出来的父类,实现了公共了函数。 // 它包含“key迭代器(keyiterator)”、“value迭代器(valueiterator)”和“entry迭代器(entryiterator)”个子类。 private abstract class hashiterator<e> implements iterator<e> { // 下一个元素 entry<k,v> next; // expectedmodcount用于实现fast-fail机制。 int expectedmodcount; // 当前索引 int index; // 当前元素 entry<k,v> current; hashiterator() { expectedmodcount = modcount; if (size > ) { // advance to first entry entry[] t = table; // 将next指向table中第一个不为null的元素。 // 这里利用了index的初始值为,从开始依次向后遍历,直到找到不为null的元素就退出循环。 while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasnext() { return next != null; } // 获取下一个元素 final entry<k,v> nextentry() { if (modcount != expectedmodcount) throw new concurrentmodificationexception(); entry<k,v> e = next; if (e == null) throw new nosuchelementexception(); // 注意!!! // 一个entry就是一个单向链表 // 若该entry的下一个节点不为空,就将next指向下一个节点; // 否则,将next指向下一个链表(也是下一个entry)的不为null的节点。 if ((next = e.next) == null) { entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } // 删除当前元素 public void remove() { if (current == null) throw new illegalstateexception(); if (modcount != expectedmodcount) throw new concurrentmodificationexception(); object k = current.key; current = null; hashmap.this.removeentryforkey(k); expectedmodcount = modcount; } } // value的迭代器 private final class valueiterator extends hashiterator<v> { public v next() { return nextentry().value; } } // key的迭代器 private final class keyiterator extends hashiterator<k> { public k next() { return nextentry().getkey(); } } // entry的迭代器 private final class entryiterator extends hashiterator<map.entry<k,v>> { public map.entry<k,v> next() { return nextentry(); } } // 返回一个“key迭代器” iterator<k> newkeyiterator() { return new keyiterator(); } // 返回一个“value迭代器” iterator<v> newvalueiterator() { return new valueiterator(); } // 返回一个“entry迭代器” iterator<map.entry<k,v>> newentryiterator() { return new entryiterator(); } // hashmap的entry对应的集合 private transient set<map.entry<k,v>> entryset = null; // 返回“key的集合”,实际上返回一个“keyset对象” public set<k> keyset() { set<k> ks = keyset; return (ks != null ? ks : (keyset = new keyset())); } // key对应的集合 // keyset继承于abstractset,说明该集合中没有重复的key。 private final class keyset extends abstractset<k> { public iterator<k> iterator() { return newkeyiterator(); } public int size() { return size; } public boolean contains(object o) { return containskey(o); } public boolean remove(object o) { return hashmap.this.removeentryforkey(o) != null; } public void clear() { hashmap.this.clear(); } } // 返回“value集合”,实际上返回的是一个values对象 public collection<v> values() { collection<v> vs = values; return (vs != null ? vs : (values = new values())); } // “value集合” // values继承于abstractcollection,不同于“keyset继承于abstractset”, // values中的元素能够重复。因为不同的key可以指向相同的value。 private final class values extends abstractcollection<v> { public iterator<v> iterator() { return newvalueiterator(); } public int size() { return size; } public boolean contains(object o) { return containsvalue(o); } public void clear() { hashmap.this.clear(); } } // 返回“hashmap的entry集合” public set<map.entry<k,v>> entryset() { return entryset(); } // 返回“hashmap的entry集合”,它实际是返回一个entryset对象 private set<map.entry<k,v>> entryset() { set<map.entry<k,v>> es = entryset; return es != null ? es : (entryset = new entryset()); } // entryset对应的集合 // entryset继承于abstractset,说明该集合中没有重复的entryset。 private final class entryset extends abstractset<map.entry<k,v>> { public iterator<map.entry<k,v>> iterator() { return newentryiterator(); } public boolean contains(object o) { if (!(o instanceof map.entry)) return false; map.entry<k,v> e = (map.entry<k,v>) o; entry<k,v> candidate = getentry(e.getkey()); return candidate != null && candidate.equals(e); } public boolean remove(object o) { return removemapping(o) != null; } public int size() { return size; } public void clear() { hashmap.this.clear(); } } // java.io.serializable的写入函数 // 将hashmap的“总的容量,实际容量,所有的entry”都写入到输出流中 private void writeobject(java.io.objectoutputstream s) throws ioexception { iterator<map.entry<k,v>> i = (size > 0) ? entryset0().iterator() : null; // write out the threshold, loadfactor, and any hidden stuff s.defaultwriteobject(); // write out number of buckets s.writeint(table.length); // write out size (number of mappings) s.writeint(size); // write out keys and values (alternating) if (i != null) { while (i.hasnext()) { map.entry<k,v> e = i.next(); s.writeobject(e.getkey()); s.writeobject(e.getvalue()); } } } private static final long serialversionuid = l; // java.io.serializable的读取函数:根据写入方式读出 // 将hashmap的“总的容量,实际容量,所有的entry”依次读出 private void readobject(java.io.objectinputstream s) throws ioexception, classnotfoundexception { // read in the threshold, loadfactor, and any hidden stuff s.defaultreadobject(); // read in number of buckets and allocate the bucket array; int numbuckets = s.readint(); table = new entry[numbuckets]; init(); // give subclass a chance to do its thing. // read in size (number of mappings) int size = s.readint(); // read the keys and values, and put the mappings in the hashmap for (int i=; i<size; i++) { k key = (k) s.readobject(); v value = (v) s.readobject(); putforcreate(key, value); } } // 返回“hashmap总的容量” int capacity() { return table.length; } // 返回“hashmap的加载因子” float loadfactor() { return loadfactor; } }
说明:
在详细介绍hashmap的代码之前,我们需要了解:hashmap就是一个散列表,它是通过“拉链法”解决哈希冲突的。
还需要再补充说明的一点是影响hashmap性能的有两个参数:初始容量(initialcapacity) 和加载因子(loadfactor)。容量 是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
第3.1部分 hashmap的“拉链法”相关内容
3.1.1 hashmap数据存储数组
transient entry[] table;
hashmap中的key-value都是存储在entry数组中的。
3.1.2 数据节点entry的数据结构
static class entry<k,v> implements map.entry<k,v> { final k key; v value; // 指向下一个节点 entry<k,v> next; final int hash; // 构造函数。 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" 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; } // 判断两个entry是否相等 // 若两个entry的“key”和“value”都相等,则返回true。 // 否则,返回false 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 (key==null ? 0 : key.hashcode()) ^ (value==null ? 0 : value.hashcode()); } public final string tostring() { return getkey() + "=" + getvalue(); } // 当向hashmap中添加元素时,绘调用recordaccess()。 // 这里不做任何处理 void recordaccess(hashmap<k,v> m) { } // 当从hashmap中删除元素时,绘调用recordremoval()。 // 这里不做任何处理 void recordremoval(hashmap<k,v> m) { } }
从中,我们可以看出 entry 实际上就是一个单向链表。这也是为什么我们说hashmap是通过拉链法解决哈希冲突的。
entry 实现了map.entry 接口,即实现getkey(), getvalue(), setvalue(v value), equals(object o), hashcode()这些函数。这些都是基本的读取/修改key、value值的函数。
第3.2部分 hashmap的构造函数
hashmap共包括4个构造函数
// 默认构造函数。 public hashmap() { // 设置“加载因子” this.loadfactor = default_load_factor; // 设置“hashmap阈值”,当hashmap中存储数据的数量达到threshold时,就需要将hashmap的容量加倍。 threshold = (int)(default_initial_capacity * default_load_factor); // 创建entry数组,用来保存数据 table = new entry[default_initial_capacity]; init(); } // 指定“容量大小”和“加载因子”的构造函数 public hashmap(int initialcapacity, float loadfactor) { if (initialcapacity < 0) throw new illegalargumentexception("illegal initial capacity: " + initialcapacity); // hashmap的最大容量只能是maximum_capacity if (initialcapacity > maximum_capacity) initialcapacity = maximum_capacity; if (loadfactor <= 0 || float.isnan(loadfactor)) throw new illegalargumentexception("illegal load factor: " + loadfactor); // find a power of 2 >= initialcapacity int capacity = 1; while (capacity < initialcapacity) capacity <<= 1; // 设置“加载因子” this.loadfactor = loadfactor; // 设置“hashmap阈值”,当hashmap中存储数据的数量达到threshold时,就需要将hashmap的容量加倍。 threshold = (int)(capacity * loadfactor); // 创建entry数组,用来保存数据 table = new entry[capacity]; init(); } // 指定“容量大小”的构造函数 public hashmap(int initialcapacity) { this(initialcapacity, default_load_factor); } // 包含“子map”的构造函数 public hashmap(map<? extends k, ? extends v> m) { this(math.max((int) (m.size() / default_load_factor) + , default_initial_capacity), default_load_factor); // 将m中的全部元素逐个添加到hashmap中 putallforcreate(m); }
第3.3部分 hashmap的主要对外接口
3.3.1 clear()
clear() 的作用是清空hashmap。它是通过将所有的元素设为null来实现的。
public void clear() { modcount++; entry[] tab = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; }
3.3.2 containskey()
containskey() 的作用是判断hashmap是否包含key。
public boolean containskey(object key) { return getentry(key) != null; }
containskey() 首先通过getentry(key)获取key对应的entry,然后判断该entry是否为null。
getentry()的源码如下:
final entry<k,v> getentry(object key) { // 获取哈希值 // hashmap将“key为null”的元素存储在table[0]位置,“key不为null”的则调用hash()计算哈希值 int hash = (key == null) ? 0 : hash(key.hashcode()); // 在“该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; }
getentry() 的作用就是返回“键为key”的键值对,它的实现源码中已经进行了说明。
这里需要强调的是:hashmap将“key为null”的元素都放在table的位置0处,即table[0]中;“key不为null”的放在table的其余位置!
3.3.3 containsvalue()
containsvalue() 的作用是判断hashmap是否包含“值为value”的元素。
public boolean containsvalue(object value) { // 若“value为null”,则调用containsnullvalue()查找 if (value == null) return containsnullvalue(); // 若“value不为null”,则查找hashmap中是否有值为value的节点。 entry[] tab = table; for (int i = ; i < tab.length ; i++) for (entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; }
从中,我们可以看出containsnullvalue()分为两步进行处理:第一,若“value为null”,则调用containsnullvalue()。第二,若“value不为null”,则查找hashmap中是否有值为value的节点。
containsnullvalue() 的作用判断hashmap中是否包含“值为null”的元素。
private boolean containsnullvalue() { entry[] tab = table; for (int i = ; i < tab.length ; i++) for (entry e = tab[i] ; e != null ; e = e.next) if (e.value == null) return true; return false; }
3.3.4 entryset()、values()、keyset()
它们3个的原理类似,这里以entryset()为例来说明。
entryset()的作用是返回“hashmap中所有entry的集合”,它是一个集合。实现代码如下:
// 返回“hashmap的entry集合” public set<map.entry<k,v>> entryset() { return entryset0(); } // 返回“hashmap的entry集合”,它实际是返回一个entryset对象 private set<map.entry<k,v>> entryset() { set<map.entry<k,v>> es = entryset; return es != null ? es : (entryset = new entryset()); } // entryset对应的集合 // entryset继承于abstractset,说明该集合中没有重复的entryset。 private final class entryset extends abstractset<map.entry<k,v>> { public iterator<map.entry<k,v>> iterator() { return newentryiterator(); } public boolean contains(object o) { if (!(o instanceof map.entry)) return false; map.entry<k,v> e = (map.entry<k,v>) o; entry<k,v> candidate = getentry(e.getkey()); return candidate != null && candidate.equals(e); } public boolean remove(object o) { return removemapping(o) != null; } public int size() { return size; } public void clear() { hashmap.this.clear(); } }
hashmap是通过拉链法实现的散列表。表现在hashmap包括许多的entry,而每一个entry本质上又是一个单向链表。那么hashmap遍历key-value键值对的时候,是如何逐个去遍历的呢?
下面我们就看看hashmap是如何通过entryset()遍历的。
entryset()实际上是通过newentryiterator()实现的。 下面我们看看它的代码:
// 返回一个“entry迭代器” iterator<map.entry<k,v>> newentryiterator() { return new entryiterator(); } // entry的迭代器 private final class entryiterator extends hashiterator<map.entry<k,v>> { public map.entry<k,v> next() { return nextentry(); } } // hashiterator是hashmap迭代器的抽象出来的父类,实现了公共了函数。 // 它包含“key迭代器(keyiterator)”、“value迭代器(valueiterator)”和“entry迭代器(entryiterator)”个子类。 private abstract class hashiterator<e> implements iterator<e> { // 下一个元素 entry<k,v> next; // expectedmodcount用于实现fast-fail机制。 int expectedmodcount; // 当前索引 int index; // 当前元素 entry<k,v> current; hashiterator() { expectedmodcount = modcount; if (size > 0) { // advance to first entry entry[] t = table; // 将next指向table中第一个不为null的元素。 // 这里利用了index的初始值为,从开始依次向后遍历,直到找到不为null的元素就退出循环。 while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasnext() { return next != null; } // 获取下一个元素 final entry<k,v> nextentry() { if (modcount != expectedmodcount) throw new concurrentmodificationexception(); entry<k,v> e = next; if (e == null) throw new nosuchelementexception(); // 注意!!! // 一个entry就是一个单向链表 // 若该entry的下一个节点不为空,就将next指向下一个节点; // 否则,将next指向下一个链表(也是下一个entry)的不为null的节点。 if ((next = e.next) == null) { entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } // 删除当前元素 public void remove() { if (current == null) throw new illegalstateexception(); if (modcount != expectedmodcount) throw new concurrentmodificationexception(); object k = current.key; current = null; hashmap.this.removeentryforkey(k); expectedmodcount = modcount; } }
当我们通过entryset()获取到的iterator的next()方法去遍历hashmap时,实际上调用的是 nextentry() 。而nextentry()的实现方式,先遍历entry(根据entry在table中的序号,从小到大的遍历);然后对每个entry(即每个单向链表),逐个遍历。
3.3.5 get()
get() 的作用是获取key对应的value,它的实现代码如下:
public v get(object key) { if (key == null) return getfornullkey(); // 获取key的hash值 int hash = hash(key.hashcode()); // 在“该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.equals(k))) return e.value; } return null; }
3.3.6 put()
put() 的作用是对外提供接口,让hashmap对象可以通过put()将“key-value”添加到hashmap中。
public v put(k key, v value) { // 若“key为null”,则将该键值对添加到table[]中。 if (key == null) return putfornullkey(value); // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。 int hash = hash(key.hashcode()); int i = indexfor(hash, table.length); for (entry<k,v> e = table[i]; e != null; e = e.next) { object k; // 若“该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; } } // 若“该key”对应的键值对不存在,则将“key-value”添加到table中 modcount++; addentry(hash, key, value, i); return null; }
若要添加到hashmap中的键值对对应的key已经存在hashmap中,则找到该键值对;然后新的value取代旧的value,并退出!
若要添加到hashmap中的键值对对应的key不在hashmap中,则将其添加到该哈希值对应的链表中,并调用addentry()。
下面看看addentry()的代码:
void addentry(int hash, k key, v value, int bucketindex) { // 保存“bucketindex”位置的值到“e”中 entry<k,v> e = table[bucketindex]; // 设置“bucketindex”位置的元素为“新entry”, // 设置“e”为“新entry的下一个节点” table[bucketindex] = new entry<k,v>(hash, key, value, e); // 若hashmap的实际大小 不小于 “阈值”,则调整hashmap的大小 if (size++ >= threshold) resize(2 * table.length); }
addentry() 的作用是新增entry。将“key-value”插入指定位置,bucketindex是位置索引。
说到addentry(),就不得不说另一个函数createentry()。createentry()的代码如下:
void createentry(int hash, k key, v value, int bucketindex) { // 保存“bucketindex”位置的值到“e”中 entry<k,v> e = table[bucketindex]; // 设置“bucketindex”位置的元素为“新entry”, // 设置“e”为“新entry的下一个节点” table[bucketindex] = new entry<k,v>(hash, key, value, e); size++; }
它们的作用都是将key、value添加到hashmap中。而且,比较addentry()和createentry()的代码,我们发现addentry()多了两句:
if (size++ >= threshold) resize(2 * table.length);
那它们的区别到底是什么呢?
阅读代码,我们可以发现,它们的使用情景不同。
(01) addentry()一般用在 新增entry可能导致“hashmap的实际容量”超过“阈值”的情况下。
例如,我们新建一个hashmap,然后不断通过put()向hashmap中添加元素;put()是通过addentry()新增entry的。
在这种情况下,我们不知道何时“hashmap的实际容量”会超过“阈值”;
因此,需要调用addentry()
(02) createentry() 一般用在 新增entry不会导致“hashmap的实际容量”超过“阈值”的情况下。
例如,我们调用hashmap“带有map”的构造函数,它绘将map的全部元素添加到hashmap中;
但在添加之前,我们已经计算好“hashmap的容量和阈值”。也就是,可以确定“即使将map中的全部元素添加到hashmap中,都不会超过hashmap的阈值”。
此时,调用createentry()即可。
3.3.7 putall()
putall() 的作用是将"m"的全部元素都添加到hashmap中,它的代码如下:
public void putall(map<? extends k, ? extends v> m) { // 有效性判断 int numkeystobeadded = m.size(); if (numkeystobeadded == 0) return; // 计算容量是否足够, // 若“当前实际容量 < 需要的容量”,则将容量x。 if (numkeystobeadded > threshold) { int targetcapacity = (int)(numkeystobeadded / loadfactor + ); if (targetcapacity > maximum_capacity) targetcapacity = maximum_capacity; int newcapacity = table.length; while (newcapacity < targetcapacity) newcapacity <<= 1; if (newcapacity > table.length) resize(newcapacity); } // 通过迭代器,将“m”中的元素逐个添加到hashmap中。 for (iterator<? extends map.entry<? extends k, ? extends v>> i = m.entryset().iterator(); i.hasnext(); ) { map.entry<? extends k, ? extends v> e = i.next(); put(e.getkey(), e.getvalue()); } }
3.3.8 remove()
remove() 的作用是删除“键为key”元素
public v remove(object key) { entry<k,v> e = removeentryforkey(key); return (e == null ? null : e.value); } // 删除“键为key”的元素 final entry<k,v> removeentryforkey(object key) { // 获取哈希值。若key为null,则哈希值为0;否则调用hash()进行计算 int hash = (key == null) ? 0 : hash(key.hashcode()); int i = indexfor(hash, table.length); entry<k,v> prev = table[i]; entry<k,v> e = prev; // 删除链表中“键为key”的元素 // 本质是“删除单向链表中的节点” 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; }
第3.4部分 hashmap实现的cloneable接口
hashmap实现了cloneable接口,即实现了clone()方法。
clone()方法的作用很简单,就是克隆一个hashmap对象并返回。
// 克隆一个hashmap,并返回object对象 public object clone() { hashmap<k,v> result = null; try { result = (hashmap<k,v>)super.clone(); } catch (clonenotsupportedexception e) { // assert false; } result.table = new entry[table.length]; result.entryset = null; result.modcount = 0; result.size = 0; result.init(); // 调用putallforcreate()将全部元素添加到hashmap中 result.putallforcreate(this); return result; }
第3.5部分 hashmap实现的serializable接口
hashmap实现java.io.serializable,分别实现了串行读取、写入功能。
串行写入函数是writeobject(),它的作用是将hashmap的“总的容量,实际容量,所有的entry”都写入到输出流中。
而串行读取函数是readobject(),它的作用是将hashmap的“总的容量,实际容量,所有的entry”依次读出
// java.io.serializable的写入函数 // 将hashmap的“总的容量,实际容量,所有的entry”都写入到输出流中 private void writeobject(java.io.objectoutputstream s) throws ioexception { iterator<map.entry<k,v>> i = (size > 0) ? entryset0().iterator() : null; // write out the threshold, loadfactor, and any hidden stuff s.defaultwriteobject(); // write out number of buckets s.writeint(table.length); // write out size (number of mappings) s.writeint(size); // write out keys and values (alternating) if (i != null) { while (i.hasnext()) { map.entry<k,v> e = i.next(); s.writeobject(e.getkey()); s.writeobject(e.getvalue()); } } } // java.io.serializable的读取函数:根据写入方式读出 // 将hashmap的“总的容量,实际容量,所有的entry”依次读出 private void readobject(java.io.objectinputstream s) throws ioexception, classnotfoundexception { // read in the threshold, loadfactor, and any hidden stuff s.defaultreadobject(); // read in number of buckets and allocate the bucket array; int numbuckets = s.readint(); table = new entry[numbuckets]; init(); // give subclass a chance to do its thing. // read in size (number of mappings) int size = s.readint(); // read the keys and values, and put the mappings in the hashmap for (int i=; i<size; i++) { k key = (k) s.readobject(); v value = (v) s.readobject(); putforcreate(key, value); } 51 }
第4部分 hashmap遍历方式
4.1 遍历hashmap的键值对
第一步:根据entryset()获取hashmap的“键值对”的set集合。
第二步:通过iterator迭代器遍历“第一步”得到的集合。
// 假设map是hashmap对象 // map中的key是string类型,value是integer类型 integer integ = null; iterator iter = map.entryset().iterator(); while(iter.hasnext()) { map.entry entry = (map.entry)iter.next(); // 获取key key = (string)entry.getkey(); // 获取value integ = (integer)entry.getvalue(); }
4.2 遍历hashmap的键
第一步:根据keyset()获取hashmap的“键”的set集合。
第二步:通过iterator迭代器遍历“第一步”得到的集合。
// 假设map是hashmap对象 // map中的key是string类型,value是integer类型 string key = null; integer integ = null; iterator iter = map.keyset().iterator(); while (iter.hasnext()) { // 获取key key = (string)iter.next(); // 根据key,获取value integ = (integer)map.get(key); }
4.3 遍历hashmap的值
第一步:根据value()获取hashmap的“值”的集合。
第二步:通过iterator迭代器遍历“第一步”得到的集合。
// 假设map是hashmap对象 // map中的key是string类型,value是integer类型 integer value = null; collection c = map.values(); iterator iter= c.iterator(); while (iter.hasnext()) { value = (integer)iter.next(); }
遍历测试程序如下:
import java.util.map; import java.util.random; import java.util.iterator; import java.util.hashmap; import java.util.hashset; import java.util.map.entry; import java.util.collection; /* * @desc 遍历hashmap的测试程序。 * (01) 通过entryset()去遍历key、value,参考实现函数: * iteratorhashmapbyentryset() * (02) 通过keyset()去遍历key、value,参考实现函数: * iteratorhashmapbykeyset() * (03) 通过values()去遍历value,参考实现函数: * iteratorhashmapjustvalues() * * */ public class hashmapiteratortest { public static void main(string[] args) { int val = ; string key = null; integer value = null; random r = new random(); hashmap map = new hashmap(); for (int i=0; i<12; i++) { // 随机获取一个[0,100)之间的数字 val = r.nextint(100); key = string.valueof(val); value = r.nextint(5); // 添加到hashmap中 map.put(key, value); system.out.println(" key:"+key+" value:"+value); } // 通过entryset()遍历hashmap的key-value iteratorhashmapbyentryset(map) ; // 通过keyset()遍历hashmap的key-value iteratorhashmapbykeyset(map) ; // 单单遍历hashmap的value iteratorhashmapjustvalues(map); } /* * 通过entry set遍历hashmap * 效率高! */ private static void iteratorhashmapbyentryset(hashmap map) { if (map == null) return ; system.out.println("\niterator hashmap by entryset"); string key = null; integer integ = null; iterator iter = map.entryset().iterator(); while(iter.hasnext()) { map.entry entry = (map.entry)iter.next(); key = (string)entry.getkey(); integ = (integer)entry.getvalue(); system.out.println(key+" -- "+integ.intvalue()); } } /* * 通过keyset来遍历hashmap * 效率低! */ private static void iteratorhashmapbykeyset(hashmap map) { if (map == null) return ; system.out.println("\niterator hashmap by keyset"); string key = null; integer integ = null; iterator iter = map.keyset().iterator(); while (iter.hasnext()) { key = (string)iter.next(); integ = (integer)map.get(key); system.out.println(key+" -- "+integ.intvalue()); } } /* * 遍历hashmap的values */ private static void iteratorhashmapjustvalues(hashmap map) { if (map == null) return ; collection c = map.values(); iterator iter= c.iterator(); while (iter.hasnext()) { system.out.println(iter.next()); } } }
第5部分 hashmap示例
下面通过一个实例学习如何使用hashmap
import java.util.map; import java.util.random; import java.util.iterator; import java.util.hashmap; import java.util.hashset; import java.util.map.entry; import java.util.collection; /* * @desc hashmap测试程序 * * */ public class hashmaptest { public static void main(string[] args) { testhashmapapis(); } private static void testhashmapapis() { // 初始化随机种子 random r = new random(); // 新建hashmap hashmap map = new hashmap(); // 添加操作 map.put("one", r.nextint(10)); map.put("two", r.nextint(10)); map.put("three", r.nextint(10)); // 打印出map system.out.println("map:"+map ); // 通过iterator遍历key-value iterator iter = map.entryset().iterator(); while(iter.hasnext()) { map.entry entry = (map.entry)iter.next(); system.out.println("next : "+ entry.getkey() +" - "+entry.getvalue()); } // hashmap的键值对个数 system.out.println("size:"+map.size()); // containskey(object key) :是否包含键key system.out.println("contains key two : "+map.containskey("two")); system.out.println("contains key five : "+map.containskey("five")); // containsvalue(object value) :是否包含值value system.out.println("contains value : "+map.containsvalue(new integer())); // remove(object key) : 删除键key对应的键值对 map.remove("three"); system.out.println("map:"+map ); // clear() : 清空hashmap map.clear(); // isempty() : hashmap是否为空 system.out.println((map.isempty()?"map is empty":"map is not empty") ); } }
(某一次)运行结果:
map:{two=7, one=9, three=6} next : two - 7 next : one - 9 next : three - 6 size:3 contains key two : true contains key five : false contains value 0 : false map:{two=7, one=9} map is empty
以上所述是小编给大家介绍的java 中的hashmap详解和使用示例_动力节点java学院整理,希望对大家有所帮助
推荐阅读
-
Java 中的HashMap详解和使用示例_动力节点Java学院整理
-
Java中struts2和spring MVC的区别_动力节点Java学院整理
-
Java中的Web MVC简介_动力节点Java学院整理
-
Java中LinkedList详解和使用示例_动力节点Java学院整理
-
Struts1和struts2的区别_动力节点Java学院整理
-
TreeSet详解和使用示例_动力节点Java学院整理
-
Java中ArrayList和LinkedList之间的区别_动力节点Java学院整理
-
详解PipedInputStream和PipedOutputStream_动力节点Java学院整理
-
Java中List Set和Map之间的区别_动力节点Java学院整理
-
File的API和常用方法详解_动力节点Java学院整理