上篇浅谈了一下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;
相关推荐
总之,"基于JavaScript的HashMap实现"这篇博客深入讲解了如何在JavaScript环境中构建一个高效、灵活的HashMap数据结构,这对于理解JavaScript的数据存储机制和提升编程技巧是非常有价值的。通过阅读和理解HashMap.js...
这篇博客将深入探讨HashMap的内部工作原理、特点以及如何在实际编程中有效地使用它。 HashMap的主要特点是其内部数据结构,它使用哈希表来存储键值对。哈希表是一种通过计算键的哈希值来快速定位元素的数据结构,这...
在JavaScript中,我们可以利用对象(object)作为HashMap的基础,因为JavaScript的对象本质上就是一个键值对的集合,其内部已经实现了哈希表的机制。 ### 自定义HashMap ```javascript class HashMap { ...
通过深入分析该类的实现细节,我们能够更好地理解其内部机制,并学会如何在实际开发中有效地利用它。 #### 类概述 `hashMap`类是基于Flex框架中的`Dictionary`类构建的。`Dictionary`是Flash中内置的一个类,它...
HashMap内部基于哈希表(也称为散列表)工作,通过键的哈希值来确定键值对在表中的位置,从而实现快速的存取。 HashMap的定义: HashMap继承自AbstractMap,并实现了Map接口,同时也实现了Cloneable和Serializable...
电话本管理系统是一个常见的应用,它允许用户存储、检索和管理联系人的信息,如姓名、电话号码、邮箱等。...在实际开发中,了解和掌握HashMap的内部原理对于优化代码性能和解决可能出现的问题至关重要。
通过对JDK7中HashMap源码的深入剖析,我们可以了解到HashMap的高效性和内部机制,这对于优化代码和理解数据结构有极大的帮助。同时,也需要注意在不同版本的JDK中,HashMap的实现可能会有所变化,例如JDK8引入了红黑...
本篇文章将通过分析一个名为"MyHashMap"的手写HashMap源码,来探讨HashMap的内部机制,帮助提升编程能力。 首先,HashMap的核心是基于哈希表的数据结构,它利用键(Key)的哈希函数将键映射到数组的特定位置,从而...
Java集合系列之HashMap源码分析 Java集合系列之HashMap源码分析是Java集合系列中的一篇非常重要的...HashMap源码分析是非常重要的,它能够帮助我们更好地理解HashMap的内部机制和实现原理,从而更好地使用HashMap。
这篇文档将深入探讨HashMap的内部机制,包括其设计理念、数据结构、哈希函数、冲突解决策略以及扩容机制。 1. **设计理念** HashMap的设计目标是实现快速的插入、删除和查找操作。它通过使用哈希表,将键(Key)...
此外,`HashMap`的容量必须是2的幂,而`ConcurrentHashMap`则允许更灵活的容量设置。 在源码层面,`HashMap`的实现相对简单,主要关注的是查找和插入的效率。而`ConcurrentHashMap`的源码则更为复杂,需要处理线程...
总的来说,HashMap是Java中高效且灵活的哈希表实现,其内部机制包括哈希函数、链地址法处理冲突、动态扩容以及非同步特性。理解HashMap的源码可以帮助开发者更好地优化程序,避免潜在的问题,并选择适合特定场景的...
本篇技术文档将深入剖析这两类数据结构的源码,帮助开发者理解其内部实现原理,提升在实际开发中的应用能力。 HashSet类是基于HashMap实现的,它不包含重复元素,并且不保证集合中元素的顺序。在HashSet中,元素的...
这篇7页的PDF文档“java集合类HashMap总结”可能是对HashMap类的深入解析,包括其原理、常用方法以及在实际开发中的应用。 HashMap的核心特性在于它的哈希函数,这个函数将键(key)转换为一个哈希码(hash code)...
HashMap是Java中最常用的集合类之一,它提供了高效的存储和检索对象键值对的能力。这篇文章将对HashMap的一些核心知识点进行深入解读,特别关注于面试中常见的问题。 1. **HashMap的默认容量** HashMap的默认容量...
在Java的集合框架中,HashMap是一个非常重要的数据结构,它提供了高效的键值对存储和查找功能。本篇文章将深入对比Java 7和Java 8中HashMap...对于开发者来说,理解HashMap的内部机制有助于写出更高效、更稳定的代码。