《数据结构》 (java版) 课件 7-5哈希表-跳表

哈希表(hashtable)1、使用桶(bucket)存储<key,value>，桶的编号为0，1，…，m-12、使用哈希函数建立<key,value>与桶的对应关系，常用的哈希函数：

index=key.hashCode()%m3、理想情况下，存、取一个<key,value>的时间复杂度为O(1)4、冲突：key1!=key2，但index1=index2

012345678910冲突键值对：｛<55，v1>,<36,v2>,<19,v3>｝哈希函数：hash(k)=k.hashCode()%m，k是Integer，则k.hashCode()=k哈希表长：m=11195536012345678910{<55，v1>,<36,v2>,<19,v3>,<3,v4>｝，3号桶出现冲突。冲突方法：线性探测假设哈希表长为11，依次插入19，1，23，14，55，68，11，82，36，10后的哈希表为：线性探测是通过形如y=ax+b的线性函数计算下一个桶号一种常用的线性探测采用函数y=h(k)+i，即如果桶h(k)被占用，则按如下的探测序列寻找空桶，h(k)+1，h(k)+2，…，h(k)+i，…,0,…，h(k)55123146811823619100123456789101121362511冲突方法：线性探测主聚集(primaryclustering)现象：012345678910插入7号桶发生冲突的概率是2号桶的4倍插入7号桶后，使得4、5、6和8、9连成了一片，造成4，5，6号桶的探测次数由4，3，2变为7，6，5冲突方法：线性探测理论上可以证明，使用线性探测时，查找失败时需要的平均的探测(比较)数：C'=(1+1/(1–𝛂)2)/2查找成功时平均的探测数：C=(1+1/(1–𝛂))/2其中，𝛂=n/m，n是哈希表中键值对的个数，𝛂叫做装载因子。如果不考虑主聚集现象，查找成功和查找失败时需要的平均的探测数为：C=-ln(1-𝛂)/𝛂C'=1/𝛂。冲突方法：线性探测55123146811823619100123456789101121362511查找成功的平均探测次数：(1+1+2+1+3+6+2+5+1+1)/10=2.3查找失败的平均探测次数：(10+9+8+7+6+5+4+3+2+11)/11=6冲突方法：线性探测𝛂=0.5查找成功的平均比较次数:1.5查找失败(插入)的平均比较次数:2.5𝛂=0.75查找成功的平均比较次数:2.5查找失败的平均比较次数:8.5𝛂=0.9查找成功的平均比较次数:5.5查找失败的平均比较次数:50线性探测课堂练习假设哈希表长为11，依次插入54，33，89，47，38，59，15，233892475938155401234567891011111131查找成功的平均探测次数：(1+1+1+1+1+1+3+1)/8=1.25查找失败的平均探测次数：(8+7+6+5+4+3+2+1+1+1+9)/11=4.27𝛂=0.73冲突方法：二次探测假设哈希表长为11，依次插入19，1，23，14，55，68，11，82，36，10后的哈希表为：二次探测是通过形如y=ax2+bx+c的线性函数计算下一个桶号一种常用的二次探测采用函数y=h(k)+i2，即如果桶h(k)被占用，则按如下的探测序列寻找空桶，h(k)+12，h(k)+22，…，h(k)+i2，…,超过m则回绕55123141182683619100123456789101121313311查找成功的平均探测次数：(1+1+2+1+3+1+3+3+1+1)/10=1.7查找不成功的平均探测次数？查找位置1的数据探测不到位置9，陷入循环冲突方法：二次探测如果采用函数y=h(k)+i2进行二次探测，理论上可以证明，当m为质数，𝛂<1/2，二次探测总能为新插入的键值对找到空桶，并且，在插入过程中没有一个桶被探测过2次。二次探测不会造成严重的主聚集现象，但存在次聚集(secondaryclustering)现象。次聚集是指由于被映射到同一个桶的键值对会在相同的位置进行探测，使得查找这些键值对时，探测次数增加。假设哈希表长为11，依次插入89，47，38，59，15894759381501234567891011113查找成功的平均探测次数：(1+1+1+1+3)/5=1.4查找失败的平均探测次数：(1+2+1+3+4+2+1+1+2+1+1)/11=1.73二次探测课堂练习分离链法(separatechaining)桶内存储多个<key,value>，并组织成一个链表理论上可以证明，查找成功的平均探测次数为，C=1+𝛂/2当𝛂≥1时，查找失败的平均探测次数为，C'=(𝛂(𝛂+3))/(2(𝛂+1))当𝛂<1时，查找失败的平均探测次数小于等于𝛂。查找成功的平均探测次数：(1+2+1+2+1+1+2+1+1+1)/10=1.3查找失败的平均探测次数：(3+3+2+3+1+2+1+1+2+1+2)/11=1.91分离链不存在主聚集现象，但存在次聚集现象，随着一个桶内的键值对数量的增加，探测次数增加。012345678910231361168558214∧∧∧10∧∧19∧∧∧∧∧∧哈希表的实现

private

static

classNode<K,V>{

private

final

int

hash;//K.hashCode()

private

finalKkey;

privateVvalue;

privateNode<K,V>next; Node(int

hash,Kkey,Vvalue,Node<K,V>next){

this.hash=hash;

this.key=key;

this.value=value;

this.next=next; } }哈希表的实现//参考了java类库的HashTable类的实现public

classCHashtable<K,V>implementsIMap<K,V>{

private

int

size;//<key,value>的个数

private

float

loadFactor;//装载因子上限

private

int

threshold;//阈值

privateNode<?,?>[]table;哈希表的实现

publicCHashtable(int

maxSize,float

loadFactor){//表长最好为质数

this.loadFactor=loadFactor;

threshold=(int)(maxSize*loadFactor);

table=newNode<?,?>[maxSize]; }

publicCHashtable(int

initialCapacity){

this(initialCapacity,0.75f);//默认装载因子0.75 }

publicCHashtable(){

this(11,0.75f);//默认表长11 }哈希表的实现

publicVget(Kkey){ Objects.requireNonNull(key);

int

hash=key.hashCode();

int

index=(hash&0x7FFFFFFF)%table.length;

for(Node<?,?>n=table[index];n!=null;n=n.next){

if((n.hash==hash)&&n.key.equals(key)){

@SuppressWarnings("unchecked") Vresult=(V)n.value;

return

result; } }

return

null; }哈希表的实现

publicVput(Kkey,Vvalue){ Objects.requireNonNull(key); Objects.requireNonNull(value);

int

hash=key.hashCode();

int

index=(hash&0x7FFFFFFF)%table.length; Node<K,V>m,n;

m=n=(Node<K,V>)table[index];

//查找是否已经存在<key,value>

for(;n!=null;n=n.next){

if((n.hash==hash)&&n.key.equals(key)){ Vold=n.value;

n.value=value;

return

old; } }

//新结点作为链表的第一个结点

table[index]=newNode<>(hash,key,value,m);

if(++size>=threshold) rehash();

return

null; }哈希表的实现

publicVremove(Kkey){ Objects.requireNonNull(key);

int

hash=key.hashCode();

int

index=(hash&0x7FFFFFFF)%table.length;

@SuppressWarnings("unchecked") Node<K,V>n=(Node<K,V>)table[index];

for(Node<K,V>prev=null;n!=null;prev=n,n=n.next){

if((n.hash==hash)&&n.key.equals(key)){

if(prev!=null)

prev.next=n.next;

else

table[index]=n.next; --size; VoldValue=n.value;

n.value=null;

n.next=null;

return

oldValue; } }

return

null; }哈希表的实现

public

voidclear(){

for(int

index=table.length;--index>=0;)

table[index]=null;//必须的，否则，内存泄漏，没有进一步帮助GC

size=0; }哈希表的实现

private

voidrehash(){

int

oldCapacity=table.length; Node<?,?>[]oldTable=table;

int

newCapacity=(oldCapacity<<1)+1;

if(newCapacity-MAX_ARRAY_SIZE>0){

if(oldCapacity==MAX_ARRAY_SIZE)

return;

newCapacity=MAX_ARRAY_SIZE; } Node<?,?>[]newTable=newNode<?,?>[newCapacity];

threshold=(int)Math.min(newCapacity*loadFactor,MAX_ARRAY_SIZE);

table=newTable;

for(int

i=oldCapacity;i-->0;){

for(Node<K,V>old=(Node<K,V>)oldTable[i];old!=null;){ Node<K,V>n=old;

old=old.next;

int

index=(n.hash&0x7FFFFFFF)%newCapacity;

n.next=(Node<K,V>)newTable[index];

newTable[index]=n; } } }从查找过程得知：1、由于冲突的产生，哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。2、哈希表查找的平均查找长度实际上并不等于零。哈希表性能分析哈希表性能分析1)哈希函数;2)处理冲突的方法;3）哈希表饱和的程度：装载因子α=n/m值的大小（n—记录数，m—表长）决定哈希表性能的因素：选择一个适当的装填因子α，使得性能限定在某个范围内。接口NavigableMapSortedMapMap接口Map接口SortedMap接口NavigableMap抽象类public

abstract

classAbstractMap<K,V>implementsMap<K,V>public

abstractclassDictionary<K,V>类public

classHashtable<K,V>

extendsDictionary<K,V>

implementsMap<K,V>,Cloneable,java.io.Serializablepublic

classHashMap<K,V>

extendsAbstractMap<K,V>

implementsMap<K,V>,Cloneable,Serializablepublic

classTreeMap<K,V>

extendsAbstractMap<K,V>

implementsNavigableMap<K,V>,Cloneable,java.io.Serializablekey，value均不能为空值线程安全(非高并发)key，value均可以为空值非线程安全get,putO(1)public

classConcurrentHashMap<K,V>extendsAbstractMap<K,V>

implementsConcurrentMap<K,V>,Serializablekey，value均可以为空值线程安全(高并发)private

static

classCollections.SynchronizedMap<K,V>

implementsMap<K,V>,Serializable有序，get,put,remove,containsKeyO(logn)“包裹”TreeMap和HashMap线程安全public

classLinkedHashMap<K,V>

extendsHashMap<K,V>

implementsMap<K,V>增加了存取序或加入序java.util.HashTable：线程安全总结桶：有各种实现方式，如链式线性表、顺序线性表、二叉树等。java.util.Map接口定义了操作，以下的类实现了该接口：java.util.HashMap:实现原理同HashTable，但是允许key和value的值为null非线程安全采用了与ArrayDeque一样的方法处理%运算桶有两种形式：链表、红黑树。高效的Map总结

static

final

inthash(Objectkey){

int

h;

return(key==null)?0:(h=key.hashCode())^(h>>>16);}没有直接使用key.hashcode，而是调用以下的函数：java.util.concurrent.ConcurrentHashMap：线程安全java.util.LinkedHashMap：扩展了HashMap除了HashMap的各桶的分离链外，还设置了一个双向链表按照次序将结点链接起来每个结点参与了一个分离链，所有的结点都还参与了双向链表。将存入表中的<key,value>用双向链表按插入次序或存取次序链接起来。HashMap有3个空函数，由put等函数调用

voidafterNodeAccess(Node<K,V>p){}

voidafterNodeInsertion(boolean

evict){}

voidafterNodeRemoval(Node<K,V>p){}LinkedHashMap只覆盖了这3个函数，但没有覆盖put等函数。用Entry扩展了Node总结跳表(SkipList)折半查找：O(logn)2024304060758020243040607580⋀head0123456跳表20243040607580∞⋀⋀20243040607580∞⋀⋀⋀012202430