Java容器HashMap与HashTable详解

2024-02-25 17:15:03 48

1、HashMap

HashMap继承抽象类AbstractMap，实现接口Map、Cloneable,Serializable接口。HashMap是一种以键值对存储数据的容器，

由数组+链表组成，其中key和value都可以为空，key的值唯一。HashMap是非线程安全的，对于键值对，

HashMap内部会将其封装成一个对应的Entry对象。HashMap的存储空间大小是可以动态改变的：

存储过程

每个对象都有一个对应的HashCode值，根据HashCode值，调用hash函数，计算出一个hash值，根据该hash值调用indexFor函数，计算出在table中的存储位置，如果该位置已经有值，则存储在该位置对应的桶中。

publicVput(Kkey,Vvalue){
if(table==EMPTY_TABLE){
inflateTable(threshold);
}
if(key==null)
returnputForNullKey(value);
inthash=hash(key);
inti=indexFor(hash,table.length);
for(Entrye=table[i];e!=null;e=e.next){
Objectk;
if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
VoldValue=e.value;
e.value=value;
e.recordAccess(this);
returnoldValue;
}
}
modCount++;
addEntry(hash,key,value,i);
returnnull;
}
publicfinalinthash(Objectk){
inth=hashSeed;
if(0!=h&&kinstanceofString){
returnsun.misc.Hashing.stringHash32((String)k);
}
h^=k.hashCode();
//ThisfunctionensuresthathashCodesthatdifferonlyby
//constantmultiplesateachbitpositionhaveabounded
//numberofcollisions(approximately8atdefaultloadfactor).
h^=(h>>>20)^(h>>>12);
returnh^(h>>>7)^(h>>>4);
}
publicfinalinthashCode(){
returnObjects.hashCode(getKey())^Objects.hashCode(getValue())
}
staticintindexFor(inth,intlength){
//assertInteger.bitCount(length)==1:"lengthmustbeanon-zeropowerof2";
returnh&(length-1);
}

获取值

首先根据key的HashCode码计算出hash值，然后调用indexFor函数计算该entry对象在table中的存储位置，遍历该位置对应桶中存储的entry对象，如果存在对象的hash值和key与要查找的相同，则返回该对象。

publicfinalEntrygetEntry(Objectkey){
if(size==0){
returnnull;
}
inthash=(key==null)?0:hash(key);
for(Entrye=table[indexFor(hash,table.length)];
e!=null;
e=e.next){
Objectk;
if(e.hash==hash&&
((k=e.key)==key||(key!=null&&key.equals(k))))
returne;
}
returnnull;
}

两map相等的判断

publicfinalbooleanequals(Objecto){
if(!(oinstanceofMap.Entry))
returnfalse;
Map.Entrye=(Map.Entry)o;
Objectk1=getKey();
Objectk2=e.getKey();
if(k1==k2||(k1!=null&&k1.equals(k2))){
Objectv1=getValue();
Objectv2=e.getValue();
if(v1==v2||(v1!=null&&v1.equals(v2)))
returntrue;
}
returnfalse;
}

自反性：对于任何非空引用值x，x.equals(x)都应返回true。

对称性：对于任何非空引用值x和y，当且仅当y.equals(x)返回true时，x.equals(y)才应返回true。

传递性：对于任何非空引用值x、y和z，如果x.equals(y)返回true，并且y.equals(z)返回

true，那么x.equals(z)应返回true。

一致性：对于任何非空引用值x和y，多次调用x.equals(y)始终返回true或始终返回false，前提是对象上

equals比较中所用的信息没有被修改。

对于任何非空引用值x，x.equals(null)都应返回false。

存储空间动态分配

HashMap的桶数目，即Entry[]table数组的长度，由于数组是内存中连续的存储单元，它的空间代价是很大的，但是它的随机存取的速度是Java集合中最快的。我们增大桶的数量，而减少Entry链表的长度，来提高从HashMap中读取数据的速度。这是典型的拿空间换时间的策略。

但是我们不能刚开始就给HashMap分配过多的桶(即Entry[]table数组起始不能太大)，这是因为数组是连续的内存空间，它的创建代价很大，况且我们不能确定给HashMap分配这么大的空间，它实际到底能够用多少，为了解决这一个问题，HashMap采用了根据实际的情况，动态地分配桶的数量。

要动态分配桶的数量，这就要求要有一个权衡的策略了，HashMap的权衡策略是这样的：

如果HashMap的大小>HashMap的容量(即Entry[]table的大小)*加载因子(经验值0.75)

则HashMap中的Entry[]table的容量扩充为当前的一倍；然后重新将以前桶中的`Entry`链表重新分配到各个桶中

上述的HashMap的容量(即Entry[]table的大小)*加载因子(经验值0.75)就是所谓的阀值(threshold)。

2、HashTable

HashTable继承Dictionary类，实现Map,Cloneable,Serializable接口，不允许key为空，采用拉链法实现与HashMap类似。

HashTable是线程安全的（但是在Collections类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的Map对象，通过该方法我们可以同步访问潜在的HashMap，对整个map对象加锁。CurrentHashMap是线程安全的，并且只对桶加锁，不会影响map对象上其它桶的操作）。

希望本文对各位朋友有所帮助

Java容器HashMap与HashTable详解

热门推荐

随机推荐