一、首先再简单重复一下Hash算法
简单的说就是一种将任意内容的输入转换成相同长度输出(有个范围,假设10位的数字,用一个称之为HashTable的容器来存放)的加密方式------hash
如(假设):
“a”---10位数1
123---10位数2
…
注意:任意内容的输入,范围是无穷无尽,肯定比相同长度输出(如10位数)要大很多,那么就会造成不同的输入,会得到相同的输出(值)----hash冲突
HashMap当然也无法避免冲突问题
二、HashMap源码片段
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;//负载因子,默认0.75
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
//使用的是Entry数组
init();
}
public V put(K key, V value) {
if (key == null)//空的情况,允许存空
return putForNullKey(value);
int hash = hash(key.hashCode());//根据key的hashCode再来计算一个hash值----根据hash冲突可以知道不同的key对应的hashCode可能一样(如果不被重写的话,Object的hashCode()生成的hashCode存放在java底层的一个大的HashTable上,不过我想JDK应该已经做过冲突处理,不会使用这么简单的hash算法,除非自己重写hashCode(),否则应该不会有冲突,真的发生冲突估计要内存溢出了)
//就算hashCode不同,通过hash()出来的hash值也可能冲突(后面会讲到)
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))) {//该位置已经有了,且key也完全是同一个,就覆盖,否则也是走下面的新开(后面会有例子)
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}//已经存在的情况
//以下是新增的情况
modCount++;
addEntry(hash, key, value, i);
return null;
}
/**
为给定的hashCode增加一个hash方法,用于抵消低质量的hash函数。这是很关键的,因为HashMap使用power-of-two长度的hash表,否则遇到冲突的hashCode无法区分
*/
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);
}
//根据hashCode及table的长度计算index
static int indexFor(int h, int length) {
return h & (length-1);
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];//先取原有的元素作为next,index冲突的时候用,形成一个“链条”
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存放自己的下一个
final int hash;
...
}
//------再看一下get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
//根据key的hashCode计算出“链条”在table中的index,再到“链条”中查找符合自己key的对象
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;
}
三、用个简单的例子详细解读HashMap的运作
public static void main(String[] args) {
HashMap map = new HashMap();
//map里包含一个Entry数组table(默认长度16)
//测试1:测试hashMap的存储 put(K,V)
//--------存放第1个对象----------
String s1 = "123";
map.put(s1, "123");
//s1的hashCode = 48690
//hash(hashCode) = 46246 ---HashMap的再次hash()
//indexFor(hash, table.length)=6 得出存放在数组中的位置为6+1(从0开始)
//虽然存放的是第一个元素,但却不是放在第一位,不是顺序存放,
//我们看table的结果为:[null, null, null, null, null, null, 123=123, null, null, null, null, null, null, null, null, null]
//读取的时候不需要按顺序对比KEY,只需通过hashCode计算出其位置就可以快速读取。
//--------存放第2个对象----------
String s2 = "123";
//s1和s2使用编译常量区,指向同一个常量
System.out.println((s1==s2) +" s1.hashCode="+s1.hashCode());//肯定是true
map.put(s2, "124");//s2和s1指向同一个对象,无疑是覆盖
//--------存放第3个对象----------
String s3 = new String("123");
//String已经重写hashCode,相同内容的字符串hashCode一定是固定相同的。
System.out.println((s1==s3) +" s3.hashCode="+s3.hashCode());//此时就是false了
//s3指向了“堆”区里的一个新建对象,但其值和s1一样,故hashCode也是一样的
map.put(s3, "125");//虽然s3和s1不是一个对象,但hashCode一样,map里只比较hashCode,故认为是同一个
System.out.println(map.size());//size只有一个
//测试2:hashMap冲突解决
//-----再存11个,正好达到threshold
for(int i=0;i<11;i++){
map.put("i"+i, i);
//有趣的事情来了
//当存到i9的时候,"i9"的hashCode=3312,hash(hashCode)=3110,----跟s3明显不同
//indexFor(hash, table.length)=6,也就是说存放在table的位置和之前的s3重了,咋办???
//继续执行,判断key的hash和值发现不是同一个,所以还是执行addEntry方法,
//addEntry也毫不客气的把位置让给"i9", }
//--此时的table为:
//[i0=0, null, null, null, i10=10, null, i9=9, null,
// i8=8, i7=7, i6=6, i5=5, i4=4, i3=3, i2=2, i1=1]
//此时的table中已经看不到s3(123=125)的存在了,那么s3哪去了呢?
//查看上面的源码段,原来每个Entry除了自己的信息外,还包含了个next(自己的下一个Entry,【可以理解为纵向的Entry,而不是table中的下一个】,
//该next是不存在table中【如果再重复,还可能再包含更深一级的next,这就跟“链”一样】)
//也就是说此时s1含在了i9中了,2个共用table的第7个位置
//我们取map元素的时候会取table中的Entry+逐级递归取每个Entry的next,这样就不会丢失了
//测试3:测试HashMap的空间扩展
//负载因子0.75,threshold(阀,table存储边界) = table容量*负载因子 = 16*0.75 = 12
//当map的实际长度超过threshold,则新建一个size*2的table,把原有的小table数据都放进来
//再存第13个,超过12,将会执行resize并transfer-data
map.put("a", "a");
//resize table----即定义一个新的2倍size大小的Entry[]数组,没什么好讲
//transfer data---将旧数组数据存放到新数组
//1、读取全部oldTable的数据【注意:是全部,含next】
//2、并不是简单的存放,将每一个Entry在新的数组中重新计算位置,再来一个indexFor(hash, table.length),这时本来2个一样的index此时很可能就不一样了,当然也不排除本来不一样变成一样的。
//HashMap代码段:
/*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);*/
//就本例解析如下:
//取到“i9”的时候,新的indexFor算出来也是6(巧合吧),放到了newTable[6]
//取“i9”的next(s3),计算s3的indexFor也正好是6(又是巧合吧,如果不是6那他们就可以撇开关系各自存储了),但是此时的newTable[6]换成了s3,而i9只能作为s3的next来存储了
//--最后table如下
//[null, null, null, null, null, null, 123=125, a=a,
//null, null, null, null, null, null, null, null, i0=0,
// null, null, null, i10=10, null, null, null, i8=8,
//i7=7, i6=6, i5=5, i4=4, i3=3, i2=2, i1=1]
//---i9不见了,s3出来了
}
推荐阅读
代码之余轻松一下:当前热门-人民的名义
相关推荐
HashMap源码深度剖析,面试必备
java hashmap 扩容因子为什么是0.75,官方给出的解释
Java HashMap类详解收藏的资料,供大家一起分享
详细分析HashMap的存储原理,key值的hash地址以及扩容
Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序 HashMap类Java SE程序...
Java集合中HashMap的简单使用,比较详细,供大家分享
提供了20道高难度的Java HashMap面试题及详细答案解析,涵盖了HashMap的内部实现原理、哈希冲突处理、扩容机制、线程安全性等方面的知识点,适合准备Java面试的开发者参考。
HashMap源码剖析共10页.pdf.zip
用数据结构的思想实现java中的类hashmap
java中HashMap详解.pdf
NULL 博文链接:https://brucexx.iteye.com/blog/491449
疫苗:Java HashMap的死循环
结合Java的HashMap中的一些优点,改进了C++ 的hash_map。 详细说明见我的博客:http://blog.csdn.net/mdj67887500/article/details/6907702
哈希简单的说就是对变量/对象的属性应用某种算法后得到的一个唯一的串,用这个串来确 定变量/对象的唯一性。一个正确的哈希函数必须遵守这个准则。
JavaHashSet和HashMap源码剖析编程开发技术共13页.pdf.zip
主要介绍了Java HashMap 如何正确遍历并删除元素的方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
java中HashMap,LinkedHashMap,TreeMap,HashTable的区别
Java语言使用hashmap实现向购物车添加删除修改商品,显示商品信息