在Java中每一个对象都有一个哈希码,这个值可以通过hashCode()方法获得。hashCode()的值和对象的equals方法息息相关,是两个对象的值是否相等的依据,所以当我们覆盖一个类的equals方法的时候也必须覆盖hashCode方法,HashMap可以看作是Java实现的哈希表。HashMap中存放的是key-value对,对应的类型为java.util.HashMap.Entry,所以在HashMap中数据都存放在一个Entry引用类型的数组table中。这里key是一个对象,为了把对象映射到table中的一个位置,我们可以通过求余法来,所以我们可以使用 [key的hashCode % table的长度]来计算位置(当然在实际操作的时候由于需要考虑table上的key的均匀分布可能需要对key的hashCode做一些处理)。
相关属性 首先肯定是需要一个数组table,作为数据结构的骨干。
transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V>{
final K key;
V value;
Entry<K,V> next;
final int hash;
......
这边定义了一个Entry数组的引用。 继续介绍几个概念把
capacity容量 是指数组table的长度
loadFactor 装载因子,是实际存放量/capacity容量 的一个比值,在代码中这个属性是描述了装载因子的最大值,默认大小为0.75
threshold(阈值)代表hashmap存放内容数量的一个临界点,
当存放量大于这个值的时候,就需要将table进行夸张,也就是新建一个两倍大的数组,并将老的元素转移过去。threshold = (int)(capacity * loadFactor);
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;
}
考虑哈希表要添加一个元素,现在假设前提是某个Entry的hash值已经计算出来,那么我们都知道哈希表下一步就是根据这个hash值
把Entry放在table数组的某个位置。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大。我们看一下Java的牛人是怎么写的。Java源码中indexFor(int h, int length) 方法用来计算某Entry对象应该保存在 table 数组的哪个索引处,其代码如下:
static int indexFor(int h, int length) {
return h & (length-1);
}
这个方法简单而又非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的 n 次方,这里就是HashMap在速度上优化的一个点。在 HashMap 构造器中有如下代码:
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方。
当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。
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);
}
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;
}
get方法其实就是将key以put时相同的方法算出在table的所在位置,然后对所在位置的链表进行遍历,找到hash值和key都相等的Entry并将value返回。
Map遍历效率问题
//方法一
void printMap(Map<String,Object> map){
Iterator<?> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
@SuppressWarnings("unchecked")
Entry<String,Object> entry = (Entry<String,Object>)iterator.next();
System.out.println("key= "+entry.getKey()+" value= "+entry.getValue());
}
}
//方法二
void printMap1(Map<String,Object> map){
Iterator<String> iterator = map.keySet().iterator();
while(iterator.hasNext()){
Object key = iterator.next();
System.out.println("key= "+key+" value= "+map.get(key) );
}
}
//方法三
void printMap2(Map<String,Object> map){
for(Map.Entry<String, Object> entry:map.entrySet()){
System.out.println("key= "+entry.getKey()+"; value="+entry.getValue());
}
请用方法一和三 , 其实方法二遍历了两遍map 严重影响效率
分享到:
相关推荐
HashMap源码深度剖析,面试必备
HashMap源码(JDK1.7,含注释)
HashMap的部分源码解析
深入浅出HashMap,源码分析, HashMap存取实现,数据结构
hashmap源码,可以看看http://blog.csdn.net/wabiaozia/article/details/50684556
HashMap数据结构,HashMap的构造方法,HashMap的put,HashMap的get
精确的版本号是jdk-7u80。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
HashMap源码流程图 一图解析HashMap源码流程 // 默认的HashMap中数组的长度 16 static final int DEFAULT_INITIAL_CAPACITY = 1 ; // aka 16 // HashMap中的数组的最大容量 static final int MAXIMUM_CAPACITY = 1 ...
主要hashMap源码,包括put,get等,其中将代码风格修改为更易懂的风格,注释也更简洁明了,可以帮助学习hashMap的同学更简单的学习hashMap
精确的版本号是jdk-8u181。想不通,竟然很多人都收费,这个明明可以在安装JDK的目录中找到啊!自己下一个JDK就可以得到。
HashMap源码实现红黑树添加元素和删除元素
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
JavaHashSet和HashMap源码剖析编程开发技术共13页.pdf.zip
HashMap源码剖析共10页.pdf.zip
易语言源码易语言HashMap类源码.rar
hashmap源码 Table Of Contents day01_JAVA语言概述与基本语法:标识符、变量也变量分类、源码_反码_补码、进制转换、编码与字符集 day02_基本语法.运算符:算术运算符、赋值运算符、比较运算符、逻辑运算符、位...
hashmap的底层及源码解析,很适合大家的学习,不要积分。