注:这里使用的是java 1.6版本。
1.HashMap继承AbstractMap,实现Map、Cloneable、Serializable接口;
2.HashMap的内部是通过数组实现的;
2-1 HashMap的内部结构
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;
2-2 Entry的定义:
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
Entry是一个链表结构;
对于一个Map中的对象,对应一个Entry;
默认初始的table大小为16,最大为1<<30,即1073741824。
3. HashMap的初始化方法。
一共有四种:
HashMap (int initiaCapacity, float loadFactor);
HashMap (int initialCapacity);
HashMap();
HashMap (Map<? Extends K, ? extends V> map);
前面三个仅仅是指定HashMap的基本参数,比如容量(capacity),扩展因子(loadFactor);第四种是通过一个已经定义的Map对HashMap进行初始化,具体的方法是通过putAllForCreate()完成。
3-1 HashMap的Map初始化
public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); }
这里首先是申请新的内存空间,新建对象;
然后在putAllForCreate()方法中,通过迭代器的循环,将参数map中的结果写入;
结果的写入通过putForCreate(K k, V v)方法完成。
3-2 HashMap的Entry插入方法
private void putForCreate(K key, V value) { int hash = (key == null) ? 0 : hash(key.hashCode()); int i = indexFor(hash, table.length); /** * Look for preexisting entry for key. This will never happen for * clone or deserialize. It will only happen for construction if the * input Map is a sorted map whose ordering is inconsistent w/ equals. */ 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; } } createEntry(hash, key, value, i); }
在putForCreate(K k, V v)方法中,首先获取新对象的hash值,计算该hash在table数组中的位置;然后检查该对象是否已经存在,如果存在,则插入失败;否则进行插入。
插入方法在createEntry中进行:
3-3 createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); size++; }
可以看到,新的元素将在链表的头部被插入。
同时,注意到HashMap中,size表示的是Entry对象的数量;而不是table数组的长度,即table.length。
4.这里有个比较巧妙的地方,即hash方法的实现以及通过hash和table长度快速定位Entry在table数组中的位置。
Hash方法是通过移位操作完成的。如下:
4-1 HashMap的hash方法
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } /** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }
5.Get方法
很简单,如下:
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); 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时,从table[0]中返回key为null时的结果;(getForNullKey())。
当key为非null时,遍历对应的链表,直到找到符合条件的Entry;如果链表遍历完成之后还没有找到,则返回空结果null。
需要说明的是,对于hash方法,不同的入参,有可能得到相同的结果,这就是所谓的“hash碰撞”。理想地,hash算法设计的目的,就是尽量减少碰撞的现象,使经过hash计算之后,结果尽量地分散,这样才能保证hash的效率最好。一种极端的情况是,所有的对象,hash的结果都相同,这种情况下,Map就退化成了链表,查询效率将大大下降。
6.containsKey方法
public boolean containsKey(Object key);
这其实也就是一种查询,除了对key进行检查之外,执行的方法和get方法一致。
7.put方法
代码如下:
public V put(K key, V value) { if (key == null) return putForNullKey(value); 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; 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; }
对于key为null的情况,将更新table[0]链表中,key为null的Entry;如果已经存在一个key为入参的entry,则更新这个entry,然后将旧的值返回;如果不存在这样的Entry,则插入一个。插入的方法为addEntry,后续马上进行说明;(putForNullKey())。
当key不为null的时候,先进行查找。通过key查找Entry,如果找到,则更新Entry的value,然后将旧的value返回;如果没有找到,则新增一个Entry。
新增Entry通过addEntry方法完成。同样是通过头部插入,新的结果被放在链表的头部。与createEntry方法不同的是,这里需要进行一次扩容判断,如果满足要求,则进行一次扩容。
addEntry方法如下:
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
扩容的条件是,当前HashMap的大小达到了阈值的设置(阈值的计算:threshold=capacity*loadFactor);扩容是将table的长度扩展为原来的两倍。
Resize方法如下:
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }
Resize方法,会重新申请新的内存保存新的结果,老的table数组将会被回收。
这里,如果旧的table的容量已经达到了设置的上限(2<<30),则新的table的threshold将会设置为最大整数值,这意味着,后续不能进行扩容了。
将旧的结果重新设置到新的table中的过程在transfer中完成。
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; 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); } } }
整个过程相当于,遍历一次所有的旧的table,以及table中每个链表的元素;然后重新写入新的table中——同样是头部插入。
这是个非常耗时的操作,所以为了性能考虑,尽量在初始化的时候,设置好合理的capacity和loadFactor,尽量避免这个方法的执行。
在最后,modCount完成一次自增操作;modCount用来记录HashMap的结构性变化的次数;在同步操作的时候用到,使失败尽可能早的发生(ConcurrentModificationException)。
同时,在put的时候,返回结果为旧的value;如果旧的value不存在,直接返回null。
8. putAll方法
public void putAll (Map<? Extends K, ? extends V> map);
将入参的map的结果全部插入HashMap中。
主要的做法就是检查容量,是否需要进行扩容;
然后通过循环,将map中的Entry对象通过循环写入。
9.remove方法
将一个元素HashMap中删除。
返回结果是被删除的Entry的值(value)。
通过removeEntryForKey方法完成。
final Entry<K,V> removeEntryForKey(Object key) { 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; 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; }
这是一个简单的链表删除的操作;这里就不进行赘述了。
不过需要注意,在HashMap的范围中进行变量的操作,比如modCount和size。
10.removeMapping
删除一个映射;相当于删除一个Entry,不过这个Entry传入的时候,类型进行了向上扩展,变成了Object。
操作的方法和removeEntryForKey一致。
11.clear方法
清理HashMap中Entry。
clear方法
public void clear() { modCount++; Entry[] tab = table; for (int i = 0; i < tab.length; i++) tab[i] = null; size = 0; }
主要是将所有的引用置空,除了modCount和size,其他的参数设置不变。
12.containsValue方法
判断HashMap中是否含有value。
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; }
这也相当于一次遍历,如果HashMap的Entry很多的话,效率会很差;慎用。
13.其他辅助访问对象
为了便于HashMap的遍历,在HashMap的类中,还定义了一些辅助的访问类。比如ValueIterator、KeyIterator、EntryIterator、HashIterator、entrySet、KeySet等等,这里就不一一列举了。
同时,为了支持序列化,HashMap也实现了readObject和writeObject方法。
相关推荐
java代码-使用java解决手写hashMap的源代码 ——学习参考资料:仅用于个人学习使用!
Java 实例 - HashMap遍历源代码-详细教程.zip
Java学生成绩管理系统源代码: imporjava.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io....
java源代码原理,深入理解HashMap原理、高可用redis集群架构、zookeeper分布式、海量数据缓存、springAOP底层源码分析等
7 匹配身份证 8 匹配邮编代码 9. 不包括特殊字符的匹配 (字符串中不包括符号 数学次方号^ 单引号' 双引号" 分号; 逗号, 帽号: 数学减号- 右尖括号> 左尖括号反斜杠\ 即空格,制表符,回车符等 10 匹配非负整数(正...
java为数据结构中的映射定义一个接口java.util.Map,有四个实现类HashMap Hashtable LinkedHashMap TreeMap用法和区别;对Map排序; 5字符串 使用String;判断一个字符串是否是合法的java标识符;使用StringBuffer;...
通过 HashMap、HashSet 的源代码分析其 Hash 存储机制1
之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也是说HashSet里面有一个HashMap(适配器模式)。因此本文将重点分析HashMap。 HashMap实现了Map...
HashMap关系数据映射技术软件源代码和jar文件。pvo是基于List这样的数据结构实现的通用DAO工具,在pvo_1.3资源文件中新增了用于客户端的pvo.js文件,用于服务端的ProcessForm类,这是一个通用的表单解析工具,是一个...
注解就相当于对源代码打的标签,给代码打上标签和删除标签对源代码没有任何影响。有的人要说了,你尽几把瞎扯,没有影响,打这些标签干毛线呢?其实不是这些标签自己起了什么作用,而且外部工具通过访问这些标签,...
用于源代码编译源文件 JAVA-->用于源文件丢虚拟机运行 JDB-->java调试器 编码表详解 ASCII:American Standard Code for Infomation Interchage美国信息交换标准代码 Unicode:万国码,0-127与ASCII一样 判断...
2.2.7 Eclipse中的源代码编辑器 26 2.2.8 Eclipse的设置窗口 26 2.2.9 Eclipse中的其他视图 27 2.3 如何使用Eclipse 28 2.3.1 在Eclipse中创建自己的第一个项目 28 2.3.2 在Eclipse中编写HelloWorld程序 29 ...
存放源代码的 com.stillcoolme.oa.struts2.action com.stillcoolme.oa.dao com.stillcoolme.oa.dao.impl com.stillcoolme.oa.service com.stillcoolme.oa.service.impl com.stillcoolme.oa.domain src.main.java ...
2.2.7 Eclipse中的源代码编辑器 26 2.2.8 Eclipse的设置窗口 26 2.2.9 Eclipse中的其他视图 27 2.3 如何使用Eclipse 28 2.3.1 在Eclipse中创建自己的第一个项目 28 2.3.2 在Eclipse中编写HelloWorld程序 29 ...
关于SWING基本功能,按键以及事件触发器使用源代码。对于初学JAVA的有较好帮助。
HashMap关系数据映射技术软件...现将PVO_v1.1软件包及其源代码对外公布,欢迎有实力的Java技术人员对其进行改进,共同打造一个高效、方便、灵活的关系映射工具。 PVO的目标是减轻你的工作负担、提高你的开发效率。
c#、java、php等多语言解决方案源代码 Wafer - 快速构建具备弹性能力的微信小程序 https://github.com/tencentyun/wafer 重要: 1.第二步,可以在5分钟内实现; 2.成本3元(腾讯云支持微信小程序2017年推广期间,3...
里面有注释,使用的技术:Session,HashMap,List有易于帮助新手开阔思路.很简单的。
60、HashMap和Hashtable的区别 2 61、List 和 Map 区别? 2 62、List, Set, Map是否继承自Collection接口? 2 63、List、Map、Set三个接口,存取元素时,各有什么特点? 2 64、说出ArrayList,Vector, LinkedList的存储...
缓慢更新一些个人学习java相关源码过程中的笔记,在这里你将不可避免地看到以下情况: 个别不懂/没想好的地方留空待补全 限于个人水平出现的解读错误 编辑错误 排版不统一 如发现有错,欢迎指正! 如果对你有用,...