Lecture 7 Hashing Table I

Hash

|---Hash function:  Division, Multiplication

|---Collision:  Chaining, Open addressing(Linear,Double hasing)

 

 

Symbol-table problem:

Table S holding n records

pointer --> key|satelite data (record)

 

 

 

Hashing:

Hash function h maps keys “randomly” into slots of table T.

Problem: Collision.

When a record to be inserted maps to an already occupied slot, a collision occurs.

Resolving collisions by chaining.

Idea: link records in same slot into list.

 

 

 

Choosing a hash function:

--Should distribute keys uniformly into slot

--Regularity in key distributions should not affect uniformly.

 

 

除法不会考虑全部的数位，如10010，如果divisor是2的话，只和最后一位有关系。

除法比乘法的计算过程多循环，即除法比乘法慢。

上面更正：

A位于2的w-1次方至w次方之间。

 

 

 

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的Lecture 7 Hashing Table I的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。