HashMap实现原理分析
概述
HashMap是Java集合框架（JavaCollectionFramework，JCF）中一个基础类，它在1998年12月，加入到Java2版本中。在此之后，Map接口本身除了在Java5中引入了泛型以外，再没有发生过明显变化。然而HashMap的实现，则为了提升性能，不断地在改变。
1.hash表的复习
在正式学习HashMap源码之前，先复习一下hash表的实现。
1.1什么是哈希表
哈希表（Hashtable，也叫散列表），是根据关键字值（key,value）直接进行访问的数据结构。也就是说，它通过把关键字映射到表中一个位置来访问的纪录，以加快查找的速度。这个映射函数叫做散列函数，存放纪录的数组叫散列表。
1.2哈希函数
1.2.1直接定址法
取关键字或关键字的某个线性函数值为哈希地址。
H(key)=key或H(key)=akey+b
1
1
1.2.2除法散列法
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词.
H(key)=key%p（p<=m）
1
1
1.2.3平方散列法
当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。
H(key)=((keyKey)>>X)<
1
1
1.2.4fibonacci散列法
和平方散列法类似，此种方法使用斐波那契数列的值作为乘数而不是自己。
对于16位整数而言，这个乘数是40503。
对于32位整数而言，这个乘数是2654435769。
对于64位整数而言，这个乘数是11400714819323198485。
H(key)=((key2654435769)>>X)<
1
1
1.3冲突解决
1.3.1开放寻址法
开放寻址法把所有的元素都存放在散列表中，也就是每个表项包含动态集合的一个元素（元素可以为NULL）。
1.在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项（连续检查是可以通过不同的算法获得偏移位），直到找到一个空槽来放置这个元素为止。
2.当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。
3.在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将此位置元素置空。因为这样做的话，会导致在无法判断此位置是否有元素。应该用个特殊的值表示该元素已经删除。
Hi=(H(key)+di)MODm,[i=1,2，…，k(k<=m-1)]
1
1
其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法:
di=1,2,3，…，m-1，称线性探测再散列。
di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）称二次探测再散列。
di=伪随机数序列，称伪随机探测再散列。
1.3.2再散列法（再散列法）
产生碰撞时，再使用另一个散列函数计算地址，直到碰撞不再发生，这种方法不易产生“聚集”，但增加了计算时间（一个地址的产生可能会经过多个散列函数的计算）
Hi=Hn(key),[n=1,2...,]
1
1
有一个包含一组哈希函数H1…Hn的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数H1。如果导致碰撞，则尝试使用H2，以此类推，直到Hn。所有的哈希函数都与H1十分相似，不同的是它们选用的乘法因子。
1.3.3拉链法
产生碰撞时，把哈希到同一个槽中的所有元素都放到一个链表中。拉链法采用额外的数据结构来处理碰撞，其将哈希表中每个位置（slot）都映射到了一个链表。
1.3.4公共溢出区
建立一个公共溢出区，当发生碰撞时，把碰撞元素放到缓冲区。
1.4负载因子
负载因子(loadfactor)，它用来衡量哈希表的空/满程度，一定程度上也可以体现查询的效率，
计算公式为:
负载因子=总键值对数/箱子个数
1
1
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是1，或者0.75等)时，哈希表将自动扩容。
2红黑树的复习
2.HashMap
2.1HashMap的定义
publicclassHashMapextendsAbstractMapimplementsMap,Cloneable,Serializable{
/
默认的哈希表的负载因子
/
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;
/
hashMap的最大容量
/
staticfinalintMAXIMUM_CAPACITY=1<<30;
/
hashMap的默认容量
/
staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16
/
HashMap要调整的下一个容量大小
/
intthreshold;
/
hashMap容量的变量
/
intthreshold;
/
哈希表负载因子的变量
/
finalfloatloadFactor;
/
构造一个具有默认初始容量(16)和默认加载因子(0.75)的HashMap
/
publicHashMap(){
this.loadFactor=DEFAULT_LOAD_FACTOR;//allotherfieldsdefaulted
}
/
构造一个带指定初始容量和默认加载因子(0.75)的HashMap。
/
publicHashMap(intinitialCapacity){
this(initialCapacity,DEFAULT_LOAD_FACTOR);
}
/
构造一个带指定初始容量和加载因子的HashMap。
/
publicHashMap(intinitialCapacity,floatloadFactor){
if(initialCapacity<0)
thrownewIllegalArgumentException("Illegalinitialcapacity:"+
initialCapacity);
if(initialCapacity>MAXIMUM_CAPACITY)
initialCapacity=MAXIMUM_CAPACITY;
if(loadFactor<=0||Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegalloadfactor:"+
loadFactor);
this.loadFactor=loadFactor;
this.threshold=tableSizeFor(initialCapacity);
}
publicHashMap(Mapm){
this.loadFactor=DEFAULT_LOAD_FACTOR;
putMapEntries(m,false);
}
/
返回给定容量大小的下一个容量。
/
staticfinalinttableSizeFor(intcap){
intn=cap-1;
n|=n>>>1;
n|=n>>>2;
n|=n>>>4;
n|=n>>>8;
n|=n>>>16;
return(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;
}
/
构造map的结构或者将map的内容全部赋值
evict初始化hashMap时是false，其余的情况为true。
/
finalvoidputMapEntries(Mapm,booleanevict){
ints=m.size();
if(s>0){
if(table==null){//pre-size初始化空间
floatft=((float)s/loadFactor)+1.0F;
intt=((ft<(float)MAXIMUM_CAPACITY)?
(int)ft:MAXIMUM_CAPACITY);
if(t>threshold)
threshold=tableSizeFor(t);
}
elseif(s>threshold)//重新调整空间
resize();
for(Map.Entrye:m.entrySet()){
Kkey=e.getKey();
Vvalue=e.getValue();
putVal(hash(key),key,value,false,evict);
}
}
}
}
HashMap实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则，而AbstractMap类提供Map接口的骨干实现，以最大限度地减少实现此接口所需的工作。
在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
2.2数据存储结构
HashMap是基于哈希表存储“Key－Value”对象应用的数据结构。存入HashMap的键必须具备两个关键函数：
（1）equals()：判断两个Key是否相同，用来保证存入的Key的唯一性；
（2）hashCode()：genjkey-value对象的Key来计算其引用在散列表中存放的位置。
transientNode[]table;
1
1
staticclassNodeimplementsMap.Entry{
finalinthash;
finalKkey;
Vvalue;
Nodenext;
Node(inthash,Kkey,Vvalue,Nodenext){
this.hash=hash;
this.key=key;
this.value=value;
this.next=next;
}
publicfinalKgetKey(){returnkey;}
publicfinalVgetValue(){returnvalue;}
publicfinalStringtoString(){returnkey+"="+value;}
publicfinalinthashCode(){
returnObjects.hashCode(key)^Objects.hashCode(value);
}
publicfinalVsetValue(VnewValue){
VoldValue=value;
value=newValue;
returnoldValue;
}
publicfinalbooleanequals(Objecto){
if(o==this)
returntrue;
if(oinstanceofMap.Entry){
Map.Entrye=(Map.Entry)o;
if(Objects.equals(key,e.getKey())&&
Objects.equals(value,e.getValue()))
returntrue;
}
returnfalse;
}
}
总结：
1.HashMap中有一个叫table的Node数组。
2.这个数组存储了Node类的对象。HashMap类有一个叫做Node的内部类。这个Node类包含了key-value作为实例变量。
3.每当往Hashmap里面存放key-value对的时候，都会为它们实例化一个Node对象，这个Node对象就会存储在前面提到的Node数组table中。根据key的hashcode()方法计算出来的hash值来决定。hash值用来计算key在Entry数组的索引。
2.2.3resize
//不使用红黑树的阀值
staticfinalintUNTREEIFY_THRESHOLD=6;
//使用红黑树的阀值
staticfinalintTREEIFY_THRESHOLD=8;
finalNode[]resize(){
Node[]oldTab=table;
intoldCap=(oldTab==null)?0:oldTab.length;
intoldThr=threshold;
intnewCap,newThr=0;
if(oldCap>0){
if(oldCap>=MAXIMUM_CAPACITY){
//hash表达到最大时，返回旧的hash表。
threshold=Integer.MAX_VALUE;
returnoldTab;
}
elseif((newCap=oldCap<<1)
oldCap>=DEFAULT_INITIAL_CAPACITY)
//容量允许的时候，内存扩大一倍
newThr=oldThr<<1;//doublethreshold
}
elseif(oldThr>0)//initialcapacitywasplacedinthreshold
//初始化带指定容量因子和碰撞因子的hashmap。
newCap=oldThr;
else{//zeroinitialthresholdsignifiesusingdefaults
//默认初始化
newCap=DEFAULT_INITIAL_CAPACITY;
newThr=(int)(DEFAULT_LOAD_FACTORDEFAULT_INITIAL_CAPACITY);
}
if(newThr==0){
floatft=(float)newCaploadFactor;
newThr=(newCap
(int)ft:Integer.MAX_VALUE);
}
threshold=newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[]newTab=(Node[])newNode[newCap];
table=newTab;
if(oldTab!=null){
//循环遍历，将旧的hash表中的数据复制到新的hash表中。
for(intj=0;j
Nodee;
if((e=oldTab[j])!=null){
oldTab[j]=null;
if(e.next==null)
newTab[e.hash&(newCap-1)]=e;
elseif(einstanceofwww.wang027.comTreeNode)
((TreeNode)e).split(this,newTab,j,oldCap);
else{//preserveorder
//拆分链表
NodeloHead=null,loTail=null;
NodehiHead=null,hiTail=null;
Nodenext;
do{
next=e.next;
//用(e.hash&oldCap)规则切割链表，为零在loHead，否则在hiHead
if((e.hash&oldCap)==0){
if(loTail==null)
loHead=e;
else
loTail.next=e;
loTail=e;
}
else{
if(hiTail==null)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
}
}while((e=next)!=null);
if(loTail!=null){
loTail.next=null;
newTab[j]=loHead;
}
if(hiTail!=null){
hiTail.next=null;
newTab[j+oldCap]=hiHead;
}
}
}
}
}
returnnewTab;
}
//拆分红黑树
finalvoidsplit(HashMapmap,Node[]tab,intindex,intbit){
TreeNodeb=this;
//Relinkintoloandhilists,preservingorder
TreeNodeloHead=null,loTail=null;
TreeNodehiHead=null,hiTail=null;
intlc=0,hc=0;
for(TreeNodee=b,next;e!=null;e=next){
next=(TreeNode)e.next;
e.next=null;
if((e.hash&bit)==0){
if((e.prev=loTail)==null)
loHead=e;
else
loTail.next=e;
loTail=e;
++lc;
}
else{
if((e.prev=hiTail)==null)
hiHead=e;
else
hiTail.next=e;
hiTail=e;
++hc;
}
}
if(loHead!=null){
//UNTREEIFY_THRESHOLD使用红黑树的阀值
if(lc<=UNTREEIFY_THRESHOLD)
tab[index]=loHead.untreeify(map);
else{
tab[index]=loHead;
if(hiHead!=null)//(elseisalreadytreeified)
loHead.treeify(tab);
}
}
if(hiHead!=null){
if(hc<=UNTREEIFY_THRESHOLD)
tab[index+bit]=hiHead.untreeify(map);
else{
tab[index+bit]=hiHead;
if(loHead!=null)
hiHead.treeify(tab);
}
}
}
//链表构造法
finalNodeuntreeify(HashMapmap){
Nodehd=null,tl=null;
for(Nodeq=this;q!=null;q=q.next){
Nodep=map.replacementNode(q,null);
if(tl==null)
hd=p;
else
tl.next=p;
tl=p;
}
returnhd;
}
//红黑树的构造方法
finalvoidtreeify(Node[]tab){
TreeNoderoot=null;
for(TreeNodex=this,next;x!=null;x=next){
next=(TreeNode)x.next;
x.left=x.right=null;
if(root==null){
x.parent=null;
x.red=false;
root=x;
}
else{
Kk=x.key;
inth=x.hash;
Classkc=null;
for(TreeNodep=root;;){
intdir,ph;
Kpk=p.key;
if((ph=p.hash)>h)
dir=-1;
elseif(ph
dir=1;
elseif((kc==null&&
(kc=comparableClassFor(k))==null)||
(dir=compareComparables(kc,k,pk))==0)
dir=tieBreakOrder(k,pk);
TreeNodexp=p;
if((p=(dir<=0)?p.left:p.right)==null){
x.parent=xp;
if(dir<=0)
xp.left=x;
else
xp.right=x;
root=balanceInsertion(root,x);
break;
}
}
}
}
moveRootToFront(tab,root);
}
当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。
http://www.cnblogs.com/huaizuo/p/5371099.html红黑树hash的计算方法。
2.2.4put操作
/
对外暴露的方法。
/
publicVput(Kkey,Vvalue){
returnputVal(hash(key),key,value,false,true);
}
/
对key进行散列
/
staticfinalinthash(Objectkey){
inth;
return(key==null)?0:(h=key.hashCode())^(h>>>16);
}
/
objec中hashcode的实现，native关键字这里代表了有操作系统进行实现。
/
publicnativeinthashCode();
/
hash-->key对应的hash值
value-->对应的值
onlyIfAbsent-->true，不改变已经存在的值
evict-->false,该表再创建模式
/
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,
booleanevict){
Node[]tab;Nodep;intn,i;
if((tab=table)==null||(n=tab.length)==0)
n=(tab=resize()).length;
if((p=tab[i=(n-1)&hash])==null)
tab[i]=newNode(hash,key,value,null);
else{
Nodee;Kk;
if(p.hash==hash&&
((k=p.key)==key||(key!=null&&key.equals(k))))
e=p;
elseif(pinstanceofTreeNode)
e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);
else{
for(intbinCount=0;;++binCount){
if((e=p.next)==null){
p.next=newNode(hash,key,value,null);
if(binCount>=TREEIFY_THRESHOLD-1)//-1for1st
treeifyBin(tab,hash);
break;
}
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
break;
p=e;
}
}
if(e!=null){//existingmappingforkey
VoldValue=e.value;
if(!onlyIfAbsent||oldValue==null)
e.value=value;
afterNodeAccess(e);
returnoldValue;
}
}
++modCount;
if(++size>threshold)
resize();
afterNodeInsertion(evict);
returnnull;
}
put方法的基本过程如下：
（1）对key的hashcode进行hash计算，获取应该保存到数组中的index。
（2）判断index所指向的数组元素是否为空，如果为空则直接插入。
（3）如果不为空，则依次查找entry中next所指定的元素，判读key是否相等，如果相等，则替换旧的值，返回。
（4）如果都不相等，则将此链表头元素赋值给待插入Node的next变量，让后将待插入元素插入到Node数组中去。
(5)Java8在没有降低哈希冲突的度的情况下，使用红黑书代替链表，
staticfinalintTREEIFY_THRESHOLD=8;
staticfinalintUNTREEIFY_THRESHOLD=6;
```
展示了Java8的HashMap在使用树和使用链表之间切换的阈值。当冲突的元素数增加到8时，链表变为树；当减少至6时，树切换为链表。中间有2个缓冲值的原因是避免频繁的切换浪费计算机资源。
Java8HashMap使用的树是红黑树，它的实现基本与JCF中的TreeMap相同。通常，树的有序性通过两个或更多对象比较大小来保证。Java8HashMap中的树也通过对象的Hash值（这个hash值与哈希桶索引值不同，索引值在这个hash值的基础上对桶大小M取模，译者注）作为对象的排序键。因为使用Hash值作为排序键打破了TotalOrdering（可以理解为数学中的小于等于关系，译者注），因此这里有一个tieBreakOrder()方法来处理这个问题。
###2.2.5get方法
publicVget(Objectkey){
Node
从上面的代码以及注释中可以看出，get操作还是比较简单的，先是根据key进行hash映射，得到其在table中的index，然后遍历真个Entry[index]链表。
##3.java关键字
###3.1transient的作用及使用方法
一个对象只要实现了Serilizable接口，这个对象就可以被序列化。将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。
1）一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
2）transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。
3）被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。
例外情况：
对象的序列化可以通过实现两种接口来实现，若实现的是Serializable接口，则所有的序列化将会自动进行，若实现的是Externalizable接口，则没有任何东西可以自动序列化，需要在writeExternal方法中进行手工指定所要序列化的变量，这与是否被transient修饰无关。
###3.2native关键字
1。native是用做java和其他语言（如c++）进行协作时用的也就是native后的函数的实现不是用java写的。
2。既然都不是java，那就别管它的源代码了
##4.hashMap与hashSet的区别
publicclassHashSet
extendsAbstractSet
implementsSet,Cloneable,java.io.Serializable
{
privatestaticfinalObjectPRESENT=newObject();
publicHashSet(){
map=newHashMap<>();
}
publicHashSet(Collectionc){
map=newHashMap<>(Math.max((int)(c.size()/.75f)+1,16));
addAll(c);
}
publicHashSet(intinitialCapacity,floatloadFactor){
map=newHashMap<>(initialCapacity,loadFactor);
}
}
由上面源程序可以看出，HashSet的实现其实非常简单，它只是封装了一个HashMap对象来存储所有的集合元素，所有放入HashSet中的集合元素实际上由HashMap的key来保存，而HashMap的value则存储了一个PRESENT，它是一个静态的Object对象。
##5.HashMap与HashTable
1
2
1
2
publicclassHashtable
1.HashTable是一个线程安全的API，它的方法通过synchronized关键字进行修饰。尽管并不推荐使用HashTable来开发一个高性能的应用，但是它确实能够保证你的应用线程安全。相反，HashMap并不保证线程安全。因此当你构建一个多线程应用时，请使用ConcurrentHashMap。
2.关联数组与数组最大的不同，就是对于每一个数据，关联数组会有一个key与之关联，当使用关联数组时，每个数据都可以通过对应的Key来获取。关联数组有许多别名，比如Map（映射）、Dictionary（字典）和Symbol-Table（符号表）。尽管名字不同，他们的含义都是相同的。
3.字典和符号表都是非常直观的术语，无须解释它们的行为。映射来自于数学领域。在函数中，一个域（集合）中的值被与另一个域（集合）中的值关联，这种关联关系叫做映射。
##6HashMap与线程安全
HashMap底层的数据结构是一个Entry数组，通过对key值进行hash映射，确定key-value对的存放位置。当多个不同key映射到同一个hash值时，它们在Entry数组中以链表的形式存在，新加入的元素会放在链表的头部。
可见HashMap的线程不安全的主要原因是HashMap的结构发生了变化，而从上一篇文章中可以知道，HashMap的结构变化发生在数组容量变更时，即当数组元素个数超过了阈值threshold=capacityloadFactor时，HashMap将resize()
#####2.2.3.1单线程下单扩容
#####2.2.3.2多线程下单扩容
#####2.2.3.3线程不安全的表现
1、多线程put操作后，get操作导致死循环。
2、多线程put非NULL元素后，get操作得到NULL值。
3、多线程put操作，导致元素丢失。
###如何安全的使用HashMap
1.Hashtable
2.ConcurrentHashMap
3.SynchronizedMap
###Hashtable
HashMap是Java1.2引进的Map接口的一个实现。HashMap是新框架中用来代替Hashtable的类，也就是说建议使用HashMap，不要使用Hashtable。
Hashtable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有public方法声明中都有synchronized关键字，而HashMap的源代码中则连synchronized的影子都没有，当然，注释除外。HashTable源码中是使用synchronized来保证线程安全的，
###ConcurrentHashMap
多线程操作要格外小心。知道JDK1.5引入了ConcurrentHashMap才使得Map重新能够安全的在多线程下操作了。
ConcurrentHashMap具体是怎么实现线程安全的呢，肯定不可能是每个方法加synchronized，那样就变成了HashTable。
从ConcurrentHashMap代码中可以看出，它引入了一个“分段锁”的概念，具体可以理解为把一个大的Map拆分成N个小的HashTable，根据key.hashCode()来决定把key放到哪个HashTable中。
在ConcurrentHashMap中，就是把Map分成了N个Segment，put和get的时候，都是现根据key.hashCode()算出放到哪个Segment中：
###SynchronizedMap
/
性能对比例程
/
publicclassCrunchifyConcurrentHashMapVsSynchronizedMap{
publicfinalstaticintTHREAD_POOL_SIZE=5;
publicstaticMapcrunchifyHashTableObject=null;
publicstaticMapcrunchifySynchronizedMapObject=null;
publicstaticMapcrunchifyConcurrentHashMapObject=null;
publicstaticvoidmain(String[]args)throwsInterruptedException{
//TestwithHashtableObject
crunchifyHashTableObject=newHashtable<>();
crunchifyPerformTest(crunchifyHashTableObject);
//TestwithsynchronizedMapObject
crunchifySynchronizedMapObject=Collections.synchronizedMap(newHashMap());
crunchifyPerformTest(crunchifySynchronizedMapObject);
//TestwithConcurrentHashMapObject
crunchifyConcurrentwww.baiyuewang.netHashMapObject=newConcurrentHashMap<>();
crunchifyPerformTest(crunchifyConcurrentHashMapObject);
}
publicstaticvoidcrunchifyPerformTest(finalMapcrunchifyThreads)throwsInterruptedException{
System.out.println("Teststartedfor:"+crunchifyThreads.getClass());
longaverageTime=0;
for(inti=0;i<5;i++){
longstartTime=System.nanoTime();
ExecutorServicecrunchifyExServer=Executors.newFixedThreadPool(THREAD_POOL_SIZE);
for(intj=0;j
crunchifyExServer.execute(newRunnable(){
@SuppressWarnings("unused")
@Override
publicvoidrun(){
for(inti=0;i<500000;i++){
IntegercrunchifyRandomNumber=(int)Math.ceil(Math.random()550000);
//Retrievevalue.Wearenotusingitanywhere
IntegercrunchifyValue=crunchifyThreads.get(String.valueOf(crunchifyRandomNumber));
//Putvalue
crunchifyThreads.put(String.valueOf(crunchifyRandomNumber),crunchifyRandomNumber);
}
}
});
}
//Makesureexecutorstops
crunchifyExServer.shutdown();
//Blocksuntilalltaskshavecompletedexecutionafterashutdownrequest
crunchifyExServer.awaitTermination(Long.MAX_VALUE,TimeUnit.DAYS);
longentTime=System.nanoTime();
longtotalTime=(entTime-startTime)/1000000L;
averageTime+=totalTime;
System.out.println("2500Kentriedadded/retrievedin"+totalTime+"ms");
}
System.out.println("For"+crunchifyThreads.getClass()+"theaveragetimeis"+averageTime/5+"ms\n");
}
}
##Redis
Redis是一个高效的key-value缓存系统，也可以理解为基于键值对的数据库。它对哈希表的设计有非常多值得学习的地方，在不影响源代码逻辑的前提下我会尽可能简化，突出重点。
数据结构
在Redis中，字典是一个dict类型的结构体，定义在src/dict.h中:
typedefstructdict{
dicththt[2];
longrehashidx;/rehashingnotinprogressifrehashidx==-1/
}dict;
这里的dictht是用于存储数据的结构体。注意到我们定义了一个长度为2的数组，它是为了解决扩容时速度较慢而引入的，其原理后面会详细介绍，rehashidx也是在扩容时需要用到。先看一下dictht的定义:
typedefstructdictht{
dictEntrytable;
unsignedlongsize;
unsignedlongused;
}dictht;
可见结构体中有一个二维数组table，元素类型是dictEntry，对应着存储的一个键值对:
typedefstructdictEntry{
voidkey;
union{
voidval;
uint64_tu64;
int64_ts64;
doubled;
}v;
structdictEntrynext;
}dictEntry;
从next指针以及二维数组可以看出，Redis的哈希表采用拉链法解决冲突。
添加元素
向字典中添加键值对的底层实现如下:
dictEntrydictAddRaw(dictd,voidkey){
intindex;
dictEntryentry;
dicththt;
if(dictIsRehashing(d))_dictRehashStep(d);
if((index=_dictKeyIndex(d,key))==-1)
returnNULL;
ht=dictIsRehashing(d)?&d->ht[1]:&d->ht[0];
entry=zmalloc(sizeof(entry));
entry->next=ht->table[index];
ht->table[index]=entry;
ht->used++;
dictSetKey(d,entry,key);
returnentry;
}
dictIsRehashing函数用来判断哈希表是否正在重新哈希。所谓的重新哈希是指在扩容时，原来的键值对需要改变位置。为了优化重哈希的体验，Redis每次只会移动一个箱子中的内容，下一节会做详细解释。
仔细阅读指针操作部分就会发现，新插入的键值对会放在箱子中链表的头部，而不是在尾部继续插入。这个细节上的改动至少带来两个好处:
找到链表尾部的时间复杂度是O(n)，或者需要使用额外的内存地址来保存链表尾部的位置。头插法可以节省插入耗时。
对于一个数据库系统来说，最新插入的数据往往更有可能频繁的被获取。头插法可以节省查找耗时。
增量式扩容
所谓的增量式扩容是指，当需要重哈希时，每次只迁移一个箱子里的链表，这样扩容时不会出现性能的大幅度下降。
为了标记哈希表正处于扩容阶段，我们在dict结构体中使用rehashidx来表示当前正在迁移哪个箱子里的数据。由于在结构体中实际上有两个哈希表，如果添加新的键值对时哈希表正在扩容，我们首先从第一个哈希表中迁移一个箱子的数据到第二个哈希表中，然后键值对会被插入到第二个哈希表中。
在上面给出的dictAddRaw方法的实现中，有两句代码:
if(dictIsRehashing(d))_dictRehashStep(d);
//…
ht=dictIsRehashing(d)?&d->ht[1]:&d->ht[0];
第二句就是用来选择插入到哪个哈希表中，第一句话则是迁移rehashidx位置上的链表。它实际上会调用dictRehash(d,1)，也就是说是单步长的迁移。dictRehash函数的实现如下:
intdictRehash(dictd,intn){
intempty_visits=n10;/Maxnumberofemptybucketstovisit./
while(n--&&d->ht[0].used!=0){
dictEntryde,nextde;
while(d->ht[0].table[d->rehashidx]==NULL){
d->rehashidx++;
if(--empty_visits==0)return1;
}
de=d->ht[0].table[d->rehashidx];
/MoveallthekeysinthisbucketfromtheoldtothenewhashHT/
while(de){
unsignedinth;
nextde=de->next;
/Gettheindexinthenewhashtable/
h=dictHashKey(d,de->key)&d->ht[1].sizemask;
de->next=d->ht[1].table[h];
d->ht[1].table[h]=de;
d->ht[0].used--;
d->ht[1].used++;
de=nextde;
}
d->ht[0].table[d->rehashidx]=NULL;
d->rehashidx++;
}
/Checkifwealreadyrehashedthewholetable.../
if(d->ht[0].used==0){
zfree(d->ht[0].table);
d->ht[0]=d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx=-1;
return0;
}
return1;
}
这段代码比较长，但是并不难理解。它由一个while循环和if语句组成。在单步迁移的情况下，最外层的while循环没有意义，而它内部又可以分为两个while循环。
第一个循环用来更新rehashidx的值，因为有些箱子为空，所以rehashidx并非每次都比原来前进一个位置，而是有可能前进几个位置，但最多不超过10。第二个循环则用来复制链表数据。
最外面的if判断中，如果发现旧哈希表已经全部完成迁移，就会释放旧哈希表的内存，同时把新的哈希表赋值给旧的哈希表，最后把rehashidx重新设置为-1，表示重哈希过程结束。
默认哈希函数
与Java不同的是，Redis提供了void类型key的哈希函数，也就是通过任何类型的key的指针都可以求出哈希值。具体算法定义在dictGenHashFunction函数中，由于代码过长，而且都是一些位运算，就不展示了。
它的实现原理是根据指针地址和这一块内存的长度，获取内存中的值，并且放入到一个数组当中，可见这个数组仅由0和1构成。然后再对这些数字做哈希运算。因此即使两个指针指向的地址不同，但只要其中内容相同，就可以得到相同的哈希值。
归纳对比
首先我们回顾一下Java和Redis的解决方案。
Java的长处在于当哈希函数不合理导致链表过长时，会使用红黑树来保证插入和查找的效率。缺点是当哈希表比较大时，如果扩容会导致瞬时效率降低。
Redis通过增量式扩容解决了这个缺点，同时拉链法的实现(放在链表头部)值得我们学习。Redis还提供了一个经过严格测试，表现良好的默认哈希函数，避免了链表过长的问题。
Objective-C的实现和Java比较类似，当我们需要重写isEqual()方法时，还需要重写hash方法。这两种语言并没有提供一个通用的、默认的哈希函数，主要是考虑到isEqual()方法可能会被重写，两个内存数据不同的对象可能在语义上被认为是相同的。如果使用默认的哈希函数就会得到不同的哈希值，这两个对象就会同时被添加到NSSet集合中，这可能违背我们的期望结果。
根据我的了解，Redis并不支持重写哈希方法，难道Redis就没有考虑到这个问题么？实际上还要从Redis的定位说起。由于它是一个高效的，Key-Value存储系统，它的key并不会是一个对象，而是一个用来唯一确定对象的标记。
一般情况下，如果要存储某个用户的信息，key的值可能是这样:user:100001。Redis只关心key的内存中的数据，因此只要是可以用二进制表示的内容都可以作为key，比如一张图片。Redis支持的数据结构包括哈希表和集合(Set)，但是其中的数据类型只能是字符串。因此Redis并不存在对象等同性的考虑，也就可以提供默认的哈希函数了。
Redis、Java、Objective-C之间的异同再次证明了一点:
“`
总结：
1.HashMap线程不安全，主要是多线程put，get是会出现同步问题；
2.多线程操作HashMap是容易出现循环链表，导致get方法调用时可能出现死循环；
3.安全的使用Map有三种方式：Hashtable，SynchronizedMap，ConcurrentHashMap。其中Hashtable不推荐使用，ConcurrentHashMap效率最高。
|
|
