[Data Structure & Algorithms in Java 6th] Ch.10 - Hash tables

---

Hash table - Github 코드

 

Hash tables

---

Hash function : stores entries (k,v) in bucket arrays A[f(k)].

   - Collision might invoke → hash code maps key k to an integer. compression function maps hash code to an integer within a range of indexes.

  - The advantage of separating hash function into two components is that mapping hash code is independent from table size.

 

   - Equivalent keys must have same hash code so they can map to the same bucket.

          > Object equals & hash code equals → compression function

 

How to avoid collision

  - Use bit representational, polynomial, Java

  - Need less

 

Java Hash Table Implementation

   - Code reading will be important.

//AbstractHashMap
public V put(K key, V value) {
        V answer = bucketPut(hashValue(key), key, value);
        if (n > capacity / 2)
            resize(2 * capacity - 1);
        return answer;
    }
 
private int hashValue(K key) {
        return (int) ((Math.abs(key.hashCode()*scale + shift) % prime) % capacity);
    }

   - Set bucket index to unique number then add Entry<K,V> to hash table.

---

Sorted Maps

---

Extension of exact search, which is finding value by given key.

Example : time stamp and occurrence of the each events. Map don't provide sort, but hash-based map ADT intentionally scatter keys to each other which seem very "near".

 

Sorted Search Tables

  - In purpose of using binary search → store map's entries in array in hash table. And sort keys in ascending order. 

  - Pros : good at indexing and find Entry. ↔ Cons : bad at put, remove (like ArrayList)

 

Two Applications of Sorted Maps

  - In condition that keys are ordered and existing reason of nearby keys have relevance to search.

  - Flight Databases

      > Get first flight in certain condition : ceilingEntry(k)

      > Return all flights in certain condition : subMap(k1, k2)

  - Maxima Sets

      > CostPerformaceDatabase : implement best(int cost) and add(int cost, int performance)

---

 

Sets

---

Similar to Maps, except not providing auxiliary of values.

 

MultiSet

  - Widely used

 

MultiMap

  - Accept duplicate keys but different values.

      > Separate entries or make secondary container for key k, {v, v1, v2, ...}

      > Value as List<V> = new ArrayList<>()

---

출처 : Data Structures and Algorithms in Java, 6th Edition 6th Edition (Michael T. Goodrich, Wiley)