Searching in an Array

• Consider a fully load array of size $n$
  • How do we search for a specific item in it?
  • What is the worst-case scenario?
  • What is the Big-O for this searching method at the worst case?

What is a Hash Map?

• Designed for improving the search efficiency in the array.
• It’s a technique to map a data to a unique address so that it can be retrieved quickly.
• It requires a key-to-address mapping process to map an input key to an address index in the array.
• It requires special way to insert and delete the key to the array.

Technical Terms

• Data to be stored to an array → Keys
• Array to store data → Hash table
• The size of the array → Hash size
  • Normally chosen to be a prime number to reduce the chance of collision.
• Formula to store data to the array → Hash function
• The location of data in the array → Address
• Using the hash function, multiple data are assigned to the same location in a hash table → Collision

Hashing Functions

• Given a key, a hash function tells its location

Division

Folding

• ง่าย ๆ ก็เหมือนเอาเลขส่วนข้างหน้ามา + กับเลขส่วนข้างหลัง แต่ก็ต้องดู $\text{C}$ อีกที

How to Handle Collisions

Separate chaining

• Separate chaining: use a list for each collided address to extend capacity of each address
  • อันนี้ไม่ค่อยได้เรียนเท่าไหร่ เหมือนว่าถ้าเจอ Collision ก็เก็บไว้ตรงนั้นแหละ

Open address

• Open address: find a new address for the new key
• Reallocate a new cell when there’s a collision: เราต้องหาช่องใหม่ให้มัน ห้ามซ้ำ
• Alternative cells are tried in succession ($i=1,2,3,…$) until the empty cell is found $$\text{H(key, i) = (H(key) +}f(i)) \% \text{ hashSize}$$
  1. Linear probing: $f(i)=i$
  2. Quadratic probing: $f(i)=i^2$
     

Load Factor

• Tell how full of your hash table

• We prefer $\lambda < 1$, when it’s approaching 1, there’s a high chance of a collision
• We should keep $\lambda<0.5$ for the open addressing and $\lambda<0.9$ for separate chaining