上篇浅谈了一下hashMap内部实现的大概模式,现在因为笔者尝试着模拟实现了下hashMap的功能,想来研究源码做个对比,因此在此记录下研究此源码的一点点感悟。
1 从put方法谈起。
摘录的hashMap中的源码如下:
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) {//遍历数组看是否存在重复的键值,若有重复,则用新的value值代替旧的value 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; }
private V putForNullKey(V value) {//key为空的情况 for (Entry<K,V> e = table[0]; e != null; e = e.next) { //遍历数组,若有key也为空的情况,则用新的value代替老的value //此处注意:hashMap中的键值是可以为空的 if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0);//若不为空,调用此方法 return null; }
加入键值对的关键代码:
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);//数组扩容 }
扩容方法:
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); } /** * Transfers all entries from current table to newTable. */ 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); } } }
通过分析源码的扩容方法可知,源码用到了一个临时变量数组src来解决把旧的table数组中的Entry全部重新散列到新数组newTable中,这正是笔者在模拟实现时遇到的问题:即要得到旧table数组中全部的元素,又要散列到一个新数组中,中间无法过度。
注:若读者还未明白,可以参看http://blog.csdn.net/mirage520/article/details/6452628;
相关推荐
HashMap内部采用数组和链表的方式存储数据,每个元素都包含键值对,通过hash函数将键映射到数组的索引位置,实现高效的查找和插入。 HashMap的性能优化策略。 HashMap在性能优化方面采取多种策略,如扩容机制、负载...
看完这篇 HashMap,和面试官扯皮就没问题了 - HashMap 概述 - HashMap 和 HashTable 的区别 - 相同点 - 不同点 - HashMap 和 HashSet 的区别 - HashMap 底层结构 - AbstractMap 类 - Map 接口 - 重要内部类...
哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串,用这个串来确 定变量/对象的唯一性。一个正确的哈希函数必须遵守这个准则。
深入探讨HashMap的底层结构、原理、扩容机制,
hashmap实例 hashmap实例hashmap实例hashmap实例
HashMap介绍和使用
hashmap相关的面试题
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
HashMap存放.doc
Hashmap详解
HashMap是一个散列桶(数组和链表),它存储的内容是键值对(key-value)映射HashMap采用了...而Hashtable则不能(原因就是equlas()方法需要对象,因为HashMap是后出的API经过处理才可以)2、HashMap的工作原理是什么?
Javascript实现和操作HashMap,压缩包里面有hashmap定义和操作的例子
hashMap排序,hashmap使用还是比较频繁。这时自己写的一个实现hashmap排序的例子
理解面向对象后的代码抽取,HashMap的二次封装,总之目的减少点代码工作量,见代码示例
HashMap类.rar
HashMap内部使用哈希表来实现,通过将键映射到哈希表中的一个位置来快速查找和插入元素。 HashMap的主要特点是: 非线程安全:如果多个线程同时访问同一个HashMap实例,可能会导致数据不一致的问题。因此,在使用...
hashmap的底层及源码解析,很适合大家的学习,不要积分。
这个文档“ HashMap详解(通俗易懂)”很好的阐述了hashmap的底层数据结构示意,希望对学习java的人有帮助
本文档主要讲述的是java中HashMap详解;HashMap和HashSet是Java Collection Framework的两个...虽然HashMap和HashSet实现的接口规范不同,但它们底层的Hash存储机制完全一样,甚至HashSet本身就采用HashMap来实现的。