Hash Table Summary and Discussion of Advanced Topics

If the hash function \(h\) is chosen well enough, and the size of \(U\) is less than or equal to the size of \(R\), it may be possible to achieve perfect hashing. For static hash tables, deterministic strategies [1] can find such an \(h\) and achieve minimal perfect hashing. For dynamic hash tables, because we cannot predict the distribution of elements in \(U\), we cannot design \(h\) in advance to achieve perfect hashing. In particular, because the elements in \(U\) change, \(U \subset S\), and the size of \(S\) is much larger than the size of \(R\), for a hash function \(h\) constructed with a deterministic strategy, there is always an adversarial set \(U\) that can make hash collisions as numerous as possible. Therefore, for dynamic hash tables, a nondeterministic strategy must be used to construct the hash function \(h\) before it is possible to guarantee avoidance of hash collisions. This problem is called the Dynamic Perfect Hashing problem. One feasible approach is to prepare a family of hash functions in advance and randomly choose one hash function from it during use. Intuitively, this family of hash functions should have some property such that inputs with the same distribution do not produce outputs with the same distribution. In this way, an adversarial strategy against one specific hash function will not work against other hash functions, so randomly selecting a hash function can resist deterministic adversarial strategies. Of course, this raises a question: during lookup, how do we know which hash function to use? This question is discussed further later in Two-way Chaining under Collision Resolution.

If there exists a set of hash functions \(H = \{h: U \rightarrow R\}\) satisfying \(\forall x, y \in U, x \ne y: \Pr_{h \in H}[h(x) = h(y)] \le 1/{|R|}\), then \(H\) is called a universal hashing family [2]. The meaning of this mathematical expression is that if any two distinct elements \(x, y\) are chosen from \(U\) and any hash function \(h\) is chosen from \(H\), then \(h(x), h(y)\) are independent (uniformly distributed).

A stronger form of universal hashing is universal_k hashing [3], which must satisfy the following condition: given k pairwise distinct elements \((x_1, ..., x_k) \in U^k\) and k hash values (which do not need to be pairwise distinct) \((y_1, ..., y_k) \in R^k\), we have

This stronger form is usually difficult to achieve, so we sometimes choose its relaxed form, \((\mu, k)\)-universal:

The closer \(\mu\) is to 1, the better.

From the discussion above, we can see that perfect hashing is difficult to achieve for dynamic hash tables, so we must consider how to handle hash collisions. Common collision resolution strategies include:

Linear Hashing [5][6] uses two hash functions at the same time to solve the dynamic resizing problem. Consider the following family of hash functions:

For any given \(x \in U\), either \(h_i(x) = h_{i - 1}(x)\) or \(h_i(c) = h_{i - 1}(c) + 2^{i - 1} N\). In general, simple modulo operations can satisfy this requirement.

When the hash array needs to expand, expansion proceeds from front to back, and the index of the bucket currently being expanded is marked as p. For positions before p, \(h_{i + 1}\) is used; for p and positions after it, \(h_i\) is still used. In this way, expansion can be very smooth: each operation expands only one bucket, without needing to rehash all elements. However, this approach has a drawback: a bucket at a relatively later position may remain very crowded, and only after many insertions will this bucket be expanded to mitigate the performance degradation. Spiral Storage handles this problem better.

Spiral Storage [5] always places more load at the front of the hash table, rather than distributing the load uniformly across the entire hash table. In this way, even though, like Linear Hashing, bucket splitting always starts from the head of the hash table, there is no problem of failing to handle very full buckets promptly.

The idea of Spiral Storage is as follows. The load of the hash table gradually decreases from front to back; when expanding, the elements in the bucket at the head of the table need to be distributed into multiple new buckets and added to the end of the hash table, while still preserving the property that the load gradually decreases from front to back. Suppose that each time one bucket is removed from the head of the table, d new buckets are added; d is called the growth factor of the hash table. Considering that the hash table grows nonlinearly, a nonlinear-growing family of hash functions should be used to map \(U\) to \(R\). It is easy to see that the exponential function satisfies this property. To satisfy the property that the load gradually decreases, \(u \in U\) can first be uniformly mapped to \(x \in [S, S + 1)\), and then the exponential function \(y = d^x \in R\) can be used. The size of \(R\) grows exponentially as \(S\) changes, and the load distribution of the elements in it decreases exponentially. When the hash table expands, elements that were originally in \(y = d^x, x \in [S, S')\) are mapped to the new interval \(y = d^x, x \in [S + 1, S' + 1)\), whose size has grown by d.

The paper [5] describes the concrete implementation details of Spiral Storage and some optimization methods.

Extendible Hashing [7] stores buckets and bucket indices separately. It uses the prefix of the key corresponding to a bucket to index it, so when expanding the size of the hash table, it is only necessary to adjust the index portion without copying all objects.

In scenarios such as Facebook F4, a read-only storage service, or Index Serving scenarios with batch updates, the Minimal Perfect Hashing strategy is suitable.

For dynamic hash table usage scenarios, if the data distribution can be known in advance or partially known, the hash function can be designed specifically to achieve perfect hashing as much as possible.

If there is no additional information about the data, only collision avoidance strategies can be considered. When a low load factor can be guaranteed, Linear Probing should be chosen as much as possible to make good use of the cache. When the load factor cannot be guaranteed, if worst-case guarantees are needed, the strategy of Separate Chaining with balanced search trees should be considered, or simply do not use a hash table. If a high load factor is desired, performance degradation should not be too severe, and some long-tail latency is acceptable, Cuckoo Hashing can be considered.

For dynamic resizing of hash tables, the Copy All strategy is generally chosen, because it imposes the fewest restrictions on the hash function and is the easiest to implement. Personally, I feel that Spiral Storage is somewhat better than Linear Hashing, for the reasons explained above in [spiral-better]. Google has an open-source implementation of Spiral Storage: https://code.google.com/p/sparsehash/ . PostgreSQL uses Linear Hashing; see https://www.postgresql.org/docs/8.0/static/sql-createindex.html .

Hash function selection is the same as in single-machine scenarios. Here we discuss only the dynamic resizing problem.

Although there were early attempts to extend Linear Hashing and Extendible Hashing to multiple machines [8][9], they were eventually dominated by consistent hashing. In multi-machine scenarios, because single-point bottlenecks are undesirable, P2P structures are used, and the larger problem is how to quickly match a request to the node that actually stores the data. This problem is categorized as how to self-organize peer nodes into some structure and perform message routing on top of it. For a summary of this area, see Paper Notes: Some Surveys on P2P. The time complexity of these routing algorithms is generally at the \(\mathcal{O}(\log n)\) level. For fast lookup scenarios in LAN environments, especially when using hash tables, we generally expect constant-level time complexity. For this, refer to [10][11], or simply cache the mapping information for all nodes.

For dynamic resizing of hash tables, I personally think Amazon Dynamo [12] did this relatively well. Recently Google also published a paper [13] that seems to guarantee an upper bound on the amount of data moved.