A：Why is 'a ≈ W/φ' special? It has to do with what happens to consecutive keys when they are hashed using the multiplicative method. As shown in Figure ‘Fibonacci Hashing’ , consecutive keys are spread out quite nicely. In fact, when we use 'a ≈ W/φ' to hash consecutive keys, the hash value for each subsequent key falls in between the two widest spaced hash values already computed. Furthermore, it is a property of the golden ratio, φ , that each subsequent hash value divides the interval into which it falls according to the golden ratio!
九章算法基礎班 Python+Java
常見的兩種解決碰撞的方法
① 拉鍊法（separate chaining）
一個Hash函數能夠将鍵轉換為數組索引，Hash算法的第二部是碰撞處理，也就是處理兩個或多個鍵的Hash值相同的情況。一種直接的辦法是将大小為 M 的數組中的每個元素指向一條連結清單，連結清單中的每個結點都存儲了Hash值為該元素的索引的鍵值對。這種方法被稱為“拉鍊法”，是以發生沖突的元素都被存儲在一個連結清單中。
public class SeparateChainingHashST<Key, Value>
{
private int N; // number of key-value pairs
private int M; // hash table size
private SequentialSearchST<Key, Value>[] st; // array of ST objects
public SeparateChainingHashST()
{
this(997);
}
public SeparateChainingHashST(int M)
{
// Create M linked lists.
this.M = M;
st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[M];
for (int i = 0; i < M; i++)
{
st[i] = new SequentialSearchST();
}
}
private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key)
{
return (Value)st[hash(key)].get(key);
}
public void put(Key key, Value val)
{
st[hash(key)].put(key, val);
}
public Iterable<Key> keys() // See Exercise 3.4.19
}
public class SequentialSearchST<Key, Value>
{
private Node first; // first node in the linked list
private class Node
{
// linked-list node
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
public Value get(Key key)
{
// Search for key, return associated value.
for (Node x = first; x != null; x = x.next)
{
if (key.equals(x.key))
{
return x.val; // search hit
}
}
return null; // search miss
}
public void put(Key key, Value val)
{
// Search for key. Update value if found; grow table if new.
for (Node x = first; x != null; x = x.next)
{
if (key.equals(x.key))
{
x.val = val;
return; // Search hit : update val.
}
}
first = new Node(key, val, first); // Search miss: add new node.
}
}
public class LinearProbingHashST<Key, Value>
{
private int N; // number of key-value pairs in the table
private int M = 16; // size of linear-probing table
private Key[] keys; // the keys
private Value[] vals; // the values
public LinearProbingHashST()
{
keys = (Key[])new Object[M];
vals = (Value[])new Object[M];
}
private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % M;
}
private void resize() // see page 474
public void put(Key key, Value val)
{
if (N >= M/2)
{
resize(2*M); // double M (see text)
}
int i;
for (i = hash(key); keys[i] != null; i = (i+1) % M)
{
if (keys[i].equals(key))
{
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
N++;
}
public Value get(Key key)
{
for (int i = hash(key); keys[i] != null; i = (i+1) % M)
{
if (keys[i].equals(key))
{
return vals[i];
}
}
return null;
}
}
public void delete(Key key)
{
if (!contains(key))
{
return;
}
int i = hash(key);
while (!key.equals(keys[i]))
{
i = (i+1) % M;
}
keys[i] = null;
vals[i] = null;
i = (i+1) % M;
while (keys[i] != null)
{
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo, valToRedo);
i = (i+1) % M;
}
N--;
if (N > 0 && N == M/8)
{
resize(M/2);
}
}
鍵簇
線性探測的平均成本取決于元素在插入數組後聚內建的一組連續的條目，也叫做鍵簇。
如圖????所示，例如，在示例中插入鍵 C 會産生一個長度為 3 的鍵簇（ A C S ）。這意味着插入 H 需要探測 4 次，因為 H 的Hash值為該鍵簇的第一個位置。
