Lecture Data Structures: Lesson 42

Chia sẻ: Hàn Thiên Ngạo | Ngày: | Loại File: PPT | Số trang:18

Thêm vào BST

Báo xấu

14
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lecture Data Structures: Lesson 42 provide students with knowledge about example hash functions; collision; find something to do with the second and subsequent values that hash to this same location; solution for handling collisions; open addressing and closed hashing;...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lecture Data Structures: Lesson 42

Lecture No.42 Data Structures Dr. Sohail Aslam
Example Hash Functions  If the keys are integers then key%T is generally a good hash function, unless the data has some undesirable features.  For example, if T = 10 and all keys end in zeros, then key%T = 0 for all keys.  In general, to avoid situations like this, T should be a prime number.
Collision Suppose our hash function gave us 0 kiwi the following values: 1 • hash("apple") = 5 hash("watermelon") = 3 2 banana hash("grapes") = 8 3 watermelon hash("cantaloupe") = 7 4 hash("kiwi") = 0 hash("strawberry") = 9 5 apple hash("mango") = 6 hash("banana") = 2 6 mango 7 cantaloupe hash("honeydew") = 6 8 grapes 9 strawberry • Now what?
Collision  When two values hash to the same array location, this is called a collision  Collisions are normally treated as “first come, first served”—the first value that hashes to the location gets it  We have to find something to do with the second and subsequent values that hash to this same location.
Solution for Handling collisions  Solution #1: Search from there for an empty location • Can stop searching when we find the value or an empty location. • Search must be wrap-around at the end.
Solution for Handling collisions  Solution #2: Use a second hash function • ...and a third, and a fourth, and a fifth, ...
Solution for Handling collisions  Solution #3: Use the array location as the header of a linked list of values that hash to this location
Solution 1: Open Addressing  This approach of handling collisions is called open addressing; it is also known as closed hashing.  More formally, cells at h0(x), h1(x), h2(x), … are tried in succession where hi(x) = (hash(x) + f(i)) mod TableSize, with f(0) = 0.  The function, f, is the collision resolution strategy.
Linear Probing  We use f(i) = i, i.e., f is a linear function of i. Thus location(x) = (hash(x) + i) mod TableSize  The collision resolution strategy is called linear probing because it scans the array sequentially (with wrap around) in search of an empty cell.
Linear Probing: insert  Suppose we want to add . . . seagull to this hash table 141  Also suppose: 142 robin • hashCode(“seagull”) = 143 143 sparrow • table[143] is not empty 144 hawk • table[143] != seagull 145 seagull • table[144] is not empty 146 • table[144] != seagull • table[145] 147 bluejay is empty 148 owl  Therefore, put seagull at . . . location 145
Linear Probing: insert  Suppose you want to add . . . hawk to this hash table 141  Also suppose 142 robin • hashCode(“hawk”) = 143 143 sparrow • table[143] is not empty 144 hawk • table[143] != hawk 145 seagull • table[144] is not empty 146 • table[144] == hawk 147 bluejay  hawk is already in the table, 148 owl so do nothing. . . .
Linear Probing: insert  Suppose: . . . • You want to add cardinal to 141 this hash table 142 robin • hashCode(“cardinal”) = 147 143 sparrow • The last location is 148 144 hawk • 147 and 148 are occupied 145 seagull  Solution: 146 • Treat the table as circular; 147 bluejay after 148 comes 0 • Hence, cardinal goes in 148 owl location 0 (or 1, or 2, or ...)
Linear Probing: find  Suppose we want to find . . . hawk in this hash table 141  We proceed as follows: 142 robin • hashCode(“hawk”) = 143 • 143 sparrow table[143] is not empty • table[143] != hawk 144 hawk • table[144] is not empty 145 seagull • table[144] == hawk (found!) 146  We use the same 147 bluejay procedure for looking 148 owl things up in the table as . . . we do for inserting them
Linear Probing and Deletion  If an item is placed in array[hash(key)+4], then the item just before it is deleted  How will probe determine that the “hole” does not indicate the item is not in the array?  Have three states for each location • Occupied • Empty (never used) • Deleted (previously used)
Clustering  One problem with linear probing technique is the tendency to form “clusters”.  A cluster is a group of items not containing any open slots  The bigger a cluster gets, the more likely it is that new values will hash into the cluster, and make it ever bigger.  Clusters cause efficiency to degrade.
Quadratic Probing  Quadratic probing uses different formula: • Use F(i) = i2 to resolve collisions • If hash function resolves to H and a search in cell H is inconclusive, try H + 12, H + 22, H + 32, …  Probe array[hash(key)+12], then array[hash(key)+22], then array[hash(key)+32], and so on • Virtually eliminates primary clusters
Collision resolution: chaining  Each table position is a No need to change position! linked list key entry key entry  Add the keys and 4 entries anywhere in the key entry key entry 10 list (front easiest) key entry 123
Collision resolution: chaining  Advantages over open addressing: key entry key entry • Simpler insertion and 4 removal key entry key entry • Array size is not a 10 limitation  Disadvantage key entry • Memory overhead is 123 large if entries are small.