hashmap是java集合框架中常用的一种数据结构,它是一种基于哈希表实现的映射表.在jdk1.8版本中,hashmap的get方法和put方法的实现与之前版本有些不同,下面我们来逐步分析其源码实现.
基本结构public class hashmap<k,v> extends abstractmap<k,v> implements map<k,v>, cloneable, serializable { // ... /** * 默认初始容量为16 */ static final int default_initial_capacity = 1 << 4; // aka 16 /** * 默认负载因子为0.75 */ static final float default_load_factor = 0.75f; /** * 最大容量:1 << 30(2的30次方) */ static final int maximum_capacity = 1 << 30; /** * 存放元素的数组,长度总是2的幂次方 */ transient hashmap.node<k,v>[] table; /** * 存放键值对的数量 */ transient int size; /** * 扩容操作的阈值 */ int threshold; /** * 负载因子,用于计算阈值 */ final float loadfactor; // ... }
get方法 /** * 根据key获取value,如果key不存在则返回null * * @param key * @return */ public v get(object key) { // 获取key对应的node节点 hashmap.node<k, v> e; // 调用getnode方法查找key对应的node节点,并将查找结果赋值给e // 如果e为null就返回null否则返回e节点的value return (e = getnode(hash(key), key)) == null ? null : e.value; } /** * 根据key的哈希值和key查找对应的node节点 * * @param hash * @param key * @return */ final hashmap.node<k, v> getnode(int hash, object key) { // 定义局部变量tab,first,e,n和k hashmap.node<k, v>[] tab; hashmap.node<k, v> first, e; int n; k k; // 如果table数据不为null且长度大于0,且第一个node节点不为空,则开始查找node节点 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 如果第一个node节点的哈希值与传入的hash值相等,且第一个node节点的key和传入的key相等,则直接返回第一个node节点 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 如果第一个node节点不是要查找的node节点,则开始遍历链表查找对应的node节点 if ((e = first.next) != null) { if (first instanceof hashmap.treenode) // 如果第一个node节点是红黑树节点,则调用红黑树节点的gettreenode方法查找对应的node节点 return ((hashmap.treenode<k, v>) first).gettreenode(hash, key); // 如果第一个node节点不是红黑树节点,则遍历链表查找对应的node节点 do { // 如果遍历到的node节点的hash值与传入的hash值相等,且node节点的key和传入的key相等,则返回对应的node节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } // 如果在table数组中没有找到对应的node节点,则返回null return null; }
get方法工作流程如下:
根据key的hashcode计算出在哈希表中的位置
遍历该位置上的链表或树,查找对应的键值对
如果找到了对应的键值对,则返回对应的value;否则返回null
put方法 /** * 向hashmap中添加一个key-value键值对 * * @param key * @param value * @return */ public v put(k key, v value) { // 根据key的哈希值和key查找对应的node节点,并添加到hashmap中 return putval(hash(key), key, value, false, true); } /** * 根据key的hash值和key添加一个键值对到hashmap中 * * @param hash * @param key * @param value * @param onlyifabsent * @param evict * @return */ final v putval(int hash, k key, v value, boolean onlyifabsent, boolean evict) { // 定义局部变量tab,p,n和i hashmap.node<k, v>[] tab; hashmap.node<k, v> p; int n, i; // 如果table数组为null或者长度为0,则先调用resize()方法初始化table数组 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 根据计算出来插入位置i插入新的键值对 if ((p = tab[i = (n - 1) & hash]) == null) // 如果插入的位置为null,则直接插入新的键值对 tab[i] = newnode(hash, key, value, null); else { hashmap.node<k, v> e; k k; // 如果插入的位置不为null,就遍历链表或树查找插入位置 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof hashmap.treenode) // 如果插入位置为红黑树节点,则调用puttreeval方法插入新的键值对 e = ((hashmap.treenode<k, v>) p).puttreeval(this, tab, hash, key, value); else { // 遍历链表,查找插入位置 for (int bincount = 0; ; ++bincount) { if ((e = p.next) == null) { // 直接在链表末尾插入新的键值对 p.next = newnode(hash, key, value, null); if (bincount >= treeify_threshold - 1) // -1 for 1st // 如果此时链表长度大于等于8,则将链表转化为红黑树 treeifybin(tab, hash); break; } // 如果找到相同key,终止循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key // 如果存在相同key,则替换对应value v oldvalue = e.value; if (!onlyifabsent || oldvalue == null) e.value = value; afternodeaccess(e); return oldvalue; } } ++modcount; if (++size > threshold) // 如果插入后的hashmap的大小大于阈值,则调用resize方法扩容hashmap resize(); afternodeinsertion(evict); return null; }
put方法工作流程如下:
根据key的hashcode值计算出在哈希表中的位置
如果该位置为空,则直接插入新的键值对
如果该位置不为空,则遍历该位置上的链表或树,查找是否已经存在对应的键值对
如果找到对应的键值对,则替换对应的value
如果没有找到对应的键值对,则将新的键值对插入到链表末尾
如果链表长度达到阈值(默认为8),则将链表转化为树
如果插入后hashmap的大小超过了阈值(默认容量的0.75),则扩容hashmap
插入完成后,执行一些必要的后续操作,例如更新修改次数等等
总的来说,hashmap的get方法和put方法都是基于哈希算法来实现键值对的查找和插入的,其中put方法需要考虑更多的情况,包括链表转换为树,扩容等等.
hashmap的容量为什么总是2的n次幂在java中,hashmap的容量总是2的n次幂的原因是为了提高hashmap的性能.
hashmap内部使用一个数组来存储键值对,当添加一个键值对时,hashmap会根据建的hashcode值计算出它在数组中的索引位置.如果数组长度不是2的n次幂,那么计算索引时就需要进行取模操作,这会影响hashmap的性能.
如果数组长度时2的n次幂,那么计算索引时可以使用位运算(&操作),这比取模操作更快.而且,hashmap的扩容操作也要求长度时2的n次幂,这样在扩容时可以简化计算,提高性能.
另外,长度为2的n次幂的数组大小还有一个优点是,它可以保证数组的不同位置发生哈希冲突的概率比较平均,这可以减少哈希冲突的发生,提高hashmap的效率.
以上就是java数据结构之hashmap源码分析的详细内容。