301重定向到新网站,在线建站,网站开发慕枫,展厅设计说明200字一、摘要
在集合系列的第一章#xff0c;咱们了解到#xff0c;Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。 应该有很多人不知道 IdentityHashMap 的存在#xff0c;其中不乏工作很多年的 Java 开发者咱们了解到Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。 应该有很多人不知道 IdentityHashMap 的存在其中不乏工作很多年的 Java 开发者本文主要从数据结构和算法层面探讨 IdentityHashMap 的实现。
二、简介
IdentityHashMap 的数据结构很简单底层实际就是一个 Object 数组但是在存储上并没有使用链表来存储而是将 K 和 V 都存放在 Object 数组上。 当添加元素的时候会根据 Key 计算得到散列位置如果发现该位置上已经有改元素直接进行新值替换如果没有直接进行存放。当元素个数达到一定阈值时Object 数组会自动进行扩容处理。
打开 IdentityHashMap 的源码可以看到 IdentityHashMap 继承了AbstractMap 抽象类实现了Map接口、可序列化接口、可克隆接口。
public class IdentityHashMapK,Vextends AbstractMapK,Vimplements MapK,V, java.io.Serializable, Cloneable
{/**默认容量大小*/private static final int DEFAULT_CAPACITY 32;/**最小容量*/private static final int MINIMUM_CAPACITY 4;/**最大容量*/private static final int MAXIMUM_CAPACITY 1 29;/**用于存储实际元素的表*/transient Object[] table;/**数组大小*/int size;/**对Map进行结构性修改的次数*/transient int modCount;/**key为null所对应的值*/static final Object NULL_KEY new Object();......
}可以看到类的底层使用了一个 Object 数组来存放元素在对象初始化时IdentityHashMap 容量大小为64
public IdentityHashMap() {//调用初始化方法init(DEFAULT_CAPACITY);
}private void init(int initCapacity) {//数组大小默认为初始化容量的2倍table new Object[2 * initCapacity];
}三、常用方法介绍
3.1、put方法
put 方法是将指定的 key, value 对添加到 map 里。该方法首先会对map做一次查找通过判断是否存在key如果有则将旧value返回将新value覆盖旧value如果没有直接插入数组长度1返回null。 源码如下
public V put(K key, V value) {//判断key是否为空如果为空初始化一个Object为keyfinal Object k maskNull(key);retryAfterResize: for (;;) {final Object[] tab table;final int len tab.length;//通过key、length获取数组小编int i hash(k, len);//循环遍历是否存在指定的keyfor (Object item; (item tab[i]) ! null;i nextKeyIndex(i, len)) {//通过判断是否数组中是否存在keyif (item k) {V oldValue (V) tab[i 1];//新value覆盖旧valuetab[i 1] value;//返回旧valuereturn oldValue;}}//数组长度 1final int s size 1;//判断是否需要扩容if (s (s 1) len resize(len))continue retryAfterResize;//更新修改次数modCount;//将k加入数组tab[i] k;//将value加入数组tab[i 1] value;size s;return null;}
}maskNull 函数判断 key 是否为空
private static Object maskNull(Object key) {return (key null ? NULL_KEY : key);
}hash 函数通过 key 获取 hash 值结合数组长度通过位运算获取数组散列下标
private static int hash(Object x, int length) {int h System.identityHashCode(x);// Multiply by -127, and left-shift to use least bit as part of hashreturn ((h 1) - (h 8)) (length - 1);
}nextKeyIndex 函数通过 hash 函数计算得到的数组散列下标进行加2因为一个 key、value 都存放在数组中所以一个 map 对象占用两个数组下标所以加2。
private static int nextKeyIndex(int i, int len) {return (i 2 len ? i 2 : 0);
}resize 函数通过数组长度进行扩容处理扩容之后的长度为当前长度的2倍
private boolean resize(int newCapacity) {//扩容后的数组长度为当前数组长度的2倍int newLength newCapacity * 2;Object[] oldTable table;int oldLength oldTable.length;if (oldLength 2 * MAXIMUM_CAPACITY) { // cant expand any furtherif (size MAXIMUM_CAPACITY - 1)throw new IllegalStateException(Capacity exhausted.);return false;}if (oldLength newLength)return false;Object[] newTable new Object[newLength];//将旧数组内容转移到新数组for (int j 0; j oldLength; j 2) {Object key oldTable[j];if (key ! null) {Object value oldTable[j1];oldTable[j] null;oldTable[j1] null;int i hash(key, newLength);while (newTable[i] ! null)i nextKeyIndex(i, newLength);newTable[i] key;newTable[i 1] value;}}table newTable;return true;
}3.2、get方法
get 方法根据指定的 key 值返回对应的 value。同样的该方法会循环遍历数组通过判断是否存在key如果有直接返回value因为 key、value 是相邻的存储在数组中所以直接在当前数组下标1即可获取 value如果没有找到直接返回null。
值得注意的地方是在循环遍历中是通过判断当前元素是否与key相同如果相同则返回value。咱们都知道在 java 中对于对象类型参数判断的是引用地址确切的说是堆内存地址所以这里判断的是key的引用地址是否相同如果相同则返回对应的 value如果不相同则返回null。 源码如下
public V get(Object key) {Object k maskNull(key);Object[] tab table;int len tab.length;int i hash(k, len);//循环遍历数组直到找到key或者数组为空为值while (true) {Object item tab[i];//通过判断当前数组元素与key相同if (item k)return (V) tab[i 1];//数组为空if (item null)return null;i nextKeyIndex(i, len);}
}3.3、remove方法
remove 的作用是通过 key 删除对应的元素。该方法会循环遍历数组通过判断是否存在key如果有直接将key、value设置为null对数组进行重新排列返回旧 value。 源码如下
public V remove(Object key) {Object k maskNull(key);Object[] tab table;int len tab.length;int i hash(k, len);while (true) {Object item tab[i];if (item k) {modCount;//数组长度减1size--;V oldValue (V) tab[i 1];//将key、value设置为nulltab[i 1] null;tab[i] null;//删除该元素后需要把原来有冲突往后移的元素移到前面来closeDeletion(i);return oldValue;}if (item null)return null;i nextKeyIndex(i, len);}
}closeDeletion 函数删除该元素后需要把原来有冲突往后移的元素移到前面来对数组进行重写排列
private void closeDeletion(int d) {// Adapted from Knuth Section 6.4 Algorithm RObject[] tab table;int len tab.length;Object item;for (int i nextKeyIndex(d, len); (item tab[i]) ! null;i nextKeyIndex(i, len) ) {int r hash(item, len);if ((i r (r d || d i)) || (r d d i)) {tab[d] item;tab[d 1] tab[i 1];tab[i] null;tab[i 1] null;d i;}}
}四、总结 IdentityHashMap 的实现不同于HashMap虽然也是数组不过IdentityHashMap中没有用到链表解决冲突的方式是计算下一个有效索引并且将数据key和value紧挨着存在map中即table[i]key、table[i1]value IdentityHashMap 允许key、value都为null当key为null的时候默认会初始化一个Object对象作为key IdentityHashMap在保存、删除、查询数据的时候以key为索引通过来判断数组中元素是否与key相同本质判断的是对象的引用地址如果引用地址相同那么在插入的时候会将value值进行替换
IdentityHashMap 测试例子
public static void main(String[] args) {MapString, String identityMaps new IdentityHashMapString, String();identityMaps.put(new String(aa), aa);identityMaps.put(new String(aa), bb);identityMaps.put(new String(aa), cc);identityMaps.put(new String(aa), cc);//输出添加的元素System.out.println(数组长度identityMaps.size() 输出结果 identityMaps);}输出结果
数组长度4输出结果{aaaa, aacc, aabb, aacc}尽管key的内容是一样的但是key的堆地址都不一样所以在插入的时候插入了4条记录。
五、参考
1、JDK1.7JDK1.8 源码
2、简书 - 骑着乌龟去看海 - IdentityHashMap源码解析
3、博客园 - leesf - IdentityHashMap源码解析
六、写到最后
最近无意间获得一份阿里大佬写的技术笔记内容涵盖 Spring、Spring Boot/Cloud、Dubbo、JVM、集合、多线程、JPA、MyBatis、MySQL 等技术知识。需要的小伙伴可以点击如下链接获取资源地址技术资料笔记。 不会有人刷到这里还想白嫖吧点赞对我真的非常重要在线求赞。加个关注我会非常感激
