数据结构与算法分析b_课件chapter5

1、Chapter 5Hashing5.1General IdeaSequention search : O(n)Binary search: O(log2n)hashing method:O(C)Address=hash(key)also called :name-address function5.1General Idea Example:.float x1, x2, x3;int beta, y2;x1 = ( beta + y2 ) / ( x2 x1 ) * y2;.H( x ) = x % 7x1 = 8849x2 = 8850x3 = 8851H( x1 ) = 8849 % 7

2、= 1H( x2 ) = 8850 % 7 = 2H( x3 ) = 8851 % 7 = 3beta = 66698465H( beta ) = 66698465 % 7 = 1y2 = 8950H( y2 ) = 8950 % 7 = 401234567betaint2002nametypeaddresslinkx1float1000x2float1004x3float1008y2int20005.1General Idea problemsFind a proper hash function How to solve a collisionSelect a suitable load

3、factor a. a=n/bn is number of elements in the hash tableb is the number of buckets in the hash tablea 1碰撞频率大a 1碰撞频率小5.2Hash Function1. 取余法H( Key ) = Key % M其中：M = 基本区长度的最大质数基本区长8162048M7132039为什么取最大质数？1) 若取偶数，如 10，100，., 2, 4, ,冲突率是比较大的；2）若取含有质因子的M，如 M=21 （3*7） 含质因子3和7，对下面的例子：key:则2.平方取中法28735146307

4、7141050关键码中含质因子7的哈希值均为7的倍数。的中间部分，其长度取决于表的大小。H( Key ) = Key2设表长= 29(2061)8(2062)8(2161)8(2162)8(1100)8= (512)10地址 000777(八进制）431054143147044734741474130412100005.2Hash Function3. 乘法杂凑函数H( Key ) = M * ( j * Key ) % 1 ) 例：设表长= 29 = (512)10地址 000777(八进制），则H( 1 ) = 29 * ( 0.618 )10 = 29 * ( 0.4743)8 = 47

5、45.2Hash Function有些书中的1. Hash1:to add up the ASCII( or Unicode ) value of the characters in the string.public static int hash( String Key, int tableSize )int hashVal = 0;for( int i = 0; i Key.length( ); i+ ) hashVal += Key.charAt( i );return hashVal % tableSize;Example:Suppose TableSize = 10007,Supp

6、ose all the keys are eight or fewer characters long,8*127=1016hash function typically can only assume value between 01016引起浪费5.2Hash Function2. Hash2:= k0 + 27*k1 + 272*k2hkeypublic static int hash( String key, int tableSize )return ( key.charAt( 0 ) + 27 * key.charAt( 1 ) +729 * key. charAt( 2 ) )

7、% tableSize;example:key = “abcmnxyz” ; H(“abc”) = ?TableSize = 10007因3个字符的词典的不同组合数只有2851，因此真正用到表的28%5.2Hash Function3.Hash3:hkey = k0 + 37k1 + 372k2+ .public static int hash( String key, int tableSize ) / goodhash fanctionint hashVal = 0;for( int i = key.length( )-1; i =0; i- ) hashVal = 37 * hashVa

8、l + key.charAt( i );hashVal %= tableSize;if( hashVal 0 ) / 函数允许溢出，这可能会引进负数hashVal += tableSize;return hashVal;5.3 how to solve a collisionlinearProbing碰撞的两个(或多个)关键码称为同义词, 即H(k1) = H(k2), k1不等于k21. Open Addressing1) linear ProbingIf hash(key)=d and the bucket is alreadyoccupied then we willexamine su

9、ccessive buckets d+1, d+2,m-1, 0, 1, 2, d-1, in thearray5.3 how to solve a collisionlinearProbingExample 1: a hash table with 11 buckets,H(k) = k % 11,Then80, 40, 65, 24, 58, 35H(80) =3,H(40) = 7,H(58) = 3,H(65) = 10,H(35) = 2H(24) = 2,5.3 how to solve a collisionlinearProbingHt012345678910Ht0123456

10、78910Ht01234567891024805835406524805840658040655.3 how to solve a collisionlinearProbingPerformance analysisthe adding sequence is 80,40,65,24,58,35 ASLsucc=(1+1+1+1+2+4)/6=10/65.3 how to solve a collisionlinearProbingexample 2 :keys : Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht,Ederlyhash( key

11、) = ord( x ) ord(A)x为取key第一个字母在字母表中的位置。例如： hash(Attlee) = 0H( Burke ) = 1 , H( Ekers ) = 4 , H( Broad ) = 1, H( Blum ) = 1, H( Attlee ) = 0 , H( Hecht ) = 7 , H(Alton ) = 0 , H( Ederly ) = 4,设散列表长m = 26 ( 025 )0123456782511231631分析比较次数：搜索成功的平均搜索长度( 1 + 1 + 2 + 3 + 1 + 1 + 6 + 3 )*1/8 = 18/8AttleeBur

12、keBroadBlumEkersAltonEderlyHecht.5.3 how to solve a collisionlinearProbingexample 3 :hash( key ) = key % 10 ; 89, 18, 49, 58, 69 012345678924411“clusteringproblem”堆积指不同的同义词表合为一张了。从而增加了插入，查找的时间。49586918895.3 how to solve a collisionlinearProbingC+ Implementation Assume that each element to be stored

13、in the hash table is of type E and has a field key of type k. the hash table is implemented using two arrays: ht and empty . emptyi is true iff hti does not have an element in it. It is defined for the deletion operation5.3 how to solve a collisionlinearProbingH(k) = k % 11,Then80, 40, 65, 24, 58, 3

14、5H(80) =3,H(40) = 7,H(58) = 3,H(65) = 10,H(35) = 2H(24) = 2,Ht012345678910要删除58，如果真的删了，则后面要查找35就找不到了。2480583540655.3 how to solve a collisionlinearProbingtemplateclass HashTablepublic:HashTable(int divisor =11);HashTable() deleteht;delete empty; bool Search(const K&k ,E& e)const; HashTable& Insert(c

15、onst E&e);private:int hSearch(const K& k)const; int D;/hash function divisor E *ht ; /hash table array bool *empty ; /1D array;5.3 how to solve a collisionlinearProbing Constructor for hashtabletemplate HashTable:HashTable(int divisor)D=divisor;ht=new ED; empty= new boolD; for(int i=0;iD;i+)emptyi=t

16、rue;5.3 how to solve a collisionlinearProbing Search function Templatebool HashTable:Search(const K&k,E&e)const/put element that matches k in e./return false if no match. int b=hSearch(k) ;if(emptyb|htb!=k)return false; e=htb;return true;5.3 how to solve a collisionlinearProbingtemplateint HashTable

17、:hSearch(const K&k)constint i=k%D;/home bucketint j=i;/start at home bucket doif(emptyj | htj= =k) return j; j=(j+1)%D; /next bucket while(j!=i);/returned to home?return j; /table full;5.3 how to solve a collisionlinearProbing Insertion into a hash tabletemplateHashTable& HashTable:Insert(const E& e

18、)K k=e;/extract keyint b=hSearch(k); if(emptyb)emptyb=false;htb=e;return *this;if(htb= =k)throw BadInput();/duplicate throw NoMem();/table full5.3 how to solve a collisionQuadratic probing2) Quadratic probingIfhash(k)=dand the bucket is alreadyoccupiedthenwe will examine successive buckets d-1, d-22

19、, d-32, the arrayexample :( 89,18, 49, 58, 69 )hash( k ) = k % 10;in012345678923311ASVsucc=(1+1+2+3+3)/549586918895.3 how to solve a collisionQuadratic probing Java Implementationelement isActiveHashEntry第一种情况： null第二种情况： 非null且该项是活动的，isActive为true第三种情况：非null 且该项标记为被删除， isActive为falsepublic interfac

20、e Hashableint hash( int tableSize );class HashEntryHashable element;boolean isActive;public HashEntry( Hashable e ) this( e, true ) ; public HashEntry( Hashable e, boolean i )element = e; isActive = i;5.3 how to solve a collisionQuadratic probingpublic class QuadraticProbingHashTablepublic Quadratic

21、ProbingHashable( )public QuadraticProbingHashable( int size ) public void makeEmpty( )public Hashable find( Hashable x )public void insert( Hashable x ) public void remove( Hashable x )public static int hash( String key, int tableSize )private static final int DEFAULT_TABLE_SIZE = 11;protected HashE

22、ntry array;private int currentSize;5.3 how to solve a collisionQuadratic probingprivate void allocateArray(int arraySize )private boolean isActive( int currentPos ) private int findPos( Hashable x )private void rehash( )private static int nextPrime( int n ) private static boolean isPrime( int n )5.3

23、 how to solve a collisionQuadratic probing Constractorpublic QuadraticProbingHashTable( )this( DEFAULT_TABLE_SIZE );public QuadraticProbingHashTable( int size )allocateArray( size );makeEmpty( );5.3 how to solve a collisionQuadratic probing Some other functionprivate void allocateArray( int arraySiz

24、e )array = new HashEntry arraySize ;public void makeEmpty( )currentSize = 0;for( int i = 0; i = array . length ) currentPos -= array . length;return currentPos;5.3 how to solve a collisionQuadratic probingprivate boolean isActive( int currentPos )return array currentPos != null &array currentPos .is

25、Active; Insert functionpublic void insert( Hashable x )int currentPos = findPos( x );if( isActive( currentPos ) ) return;array currentPos = new HashEntry( x, true ); if( +currentSize array . length / 2 )rehash( );5.3 how to solve a collisionQuadratic probing Remove functionpublic final void remove(

26、Hashable x )int currentPos = findPos( x );if( isActive( currentPos) )array currentPos . isActive = false;5.3 how to solve a collisionDouble Hashing3) Double HashingIf hash1(k)=d and the bucket is already occupied then we will counting hash2(k) =c, examine successive buckets d+c, d+2c, d+3c, in the a

27、rrayexample:hash1(k) = k % 10; hash2(k) = R (k % R ); 其中R 表的70% 时,可再散列.即, 取比(2*原表长=14)大的质数17再散列.6%17=6,15%17=15,23%17=6,24%17=7,13%17=136152324130rehashing1234501234566789101112131415615232413623241315rehashingprivate void rehash( )HashEntry oldArray = array ;allocateArray(nextPrime( 2* oldArray.len

28、gth ) );currentSize = 0;for( int i = 0; i oldArray.length;i+ )if( oldArray i != null & oldArray i . isActive ) insert( oldArray i . Element );5.4how to solve a collisionSeparate Chaining2. Separate Chaininght01234567890, 1, 4, 9, 16, 25, 36, 49, 64, 81Hash(x) = x % 1094916362546418105.4how to solve

29、a collisionSeparate Chainingpublic class SeparateChainingHashTablepublic SeparateChainingHashTable( )public SeparateChainingHashTable( int size ) public void insert( Hashable x )public void remove( Hashable x ) public Hashable find( Hashable x ) public void makeEmpty( )public static int hash( String

30、 key, int tableSize )private static final int DEFAULT_TABLE_SIZE = 101;private LinkedList theLists;private static int nextPrime( int n )private static boolean isPrime( int n )5.4how to solve a collisionSeparate Chainingpublic interface Hashableint hash( int tableSize );public class Employee implemen

31、ts Hashablepublic int hash( int tableSize ) return SeparateChainingHashTable.hash( name, tableSize ); public boolean equals( object rhs ) return name.equals( ( Employee) rhs ).name ); private String name;private double salary; private int seniority;5.4how to solve a collisionSeparate Chainingpublic SeparateChainingHashTable( )this( DEFAULT_TABLE_SIZE );public SeparateChainingHashTable( int size ) theLists = new LinkedList nextP