# SAHA: A String Adaptive Hash Table for Analytical Databases
## 3 Constructs
We only need to check the first integer, that is key[0] == 0 in Figure 5. This gives considerable improvements, especially for Hash Table S3, which contains three integers per key. * **Automatic ownership handling for Hash Table L**. For long strings, we copy the string data into String Arena to hold the ownership of string key when successfully inserted. This requires the insertion method to return the reference of the inserted string key in order to modify the string pointer to the new location in String Arena. However, it is expensive to return the key reference, since strings are also stored as integers in SAHA; returning references universally would require constructing temporary strings. To address this, we augment the string key with an optional memory pool reference and allow the hash table to decide when the string key needs to be parsed into the memory pool. It is used in Hash Table L that automatically parses strings when newly inserted. * **CRC32 hashing with memory loading optimization**. Cyclic redundancy check (CRC) is an error-detecting code. It hashes a stream of bytes with as few collisions as possible, which makes it a good candidate as a hash function. Modern CPUs provide CRC32 native instructions that compute the CRC value of eight bytes in a few cycles. As a result, we can use the memory loading technique in the string dispatcher to do CRC32 hashing efficiently. ```
voiddispatchEmplace(StringRef key,Slot*&slot){ inttail=(-key.size&7)*8; union{StringKey8}k8;StringKey16k16;StringKey24k24;uint64_tn[3];}; switch(key.size){ case0: Hash_Table_S0.emplace(0,slot); case1..8; if(key.pointer&2048)==0){ memcpy(&n[0],key.pointer,8);n[0]&=-1>>tail;} else{ memcpy(&n[0],key.pointer+key.size-8,8);n[0]>>=tail;} if(n[0]<65536)Hash_Table_S0.emplace(k8,slot); elseHash_Table_S1.emplace(k8,slot); case9..16; memcpy(&n[0],key.pointer,8); memcpy(&n[1],key.pointer+key.size-8,8); n[1]>>=s; Hash_Table_S2.emplace(k16,slot); case17..24; memcpy(&n[0],key.pointer,16); memcpy(&n[2],key.pointer+key.size-8,8); n[2]>>=s; Hash_Table_S3.emplace(k24,slot); default: Hash_Table_L.emplace(key,slot); }
```  
**Listing 1**. Implementatation of string dispatcher for the emplace routine in pseudo C++. To better understand the effectiveness of our optimizations, we discuss the cost models of the hash table's find and emplace routines respectively. For the find routine, it mainly consists of two steps: (a) computing the current key's hash value to lookup its conflicting chain, denoted as \(H\); and (b) probing the chain to find whether there is a matching key, denoted as \(P\). The complexity of the probing process is related to the average length of the conflicting chain, denoted as \(alpha\). We can further divide the probing process into loading each slot's memory content \(P_{L}\) and doing key comparisons \(P_{C}\)After adding the complexity \(O\) of other maintenance operations such as rehashing, we can formulate the runtime complexity \(T_{find}\) of a unsuccessful find operation as Equation (1). \[T_{find}=O+H+alpha*(P_{L}+P_{C}) \tag{1}\]  
A successful find has almost the same complexity with a smaller \(alpha\); that is, it can finish earlier when a match is found. An unsuccessful (we call it unsuccessful because the emplace fails to store the key when a same key is found in the hash table) emplace operation is identical to a successful find, while a successful emplace has one additional step: after finding an empty slot, it needs to store the element being emplaced, denoted as \(S\). For string values, it means parsing the string data into the hash table's memory pool, \(S_{P}\), and writing the updated string pointer into the slot, \(S_{W}\). Thus, the total runtime complexity \(T_{emplace}\) of a successful emplace operation is higher than a find operation, as shown in Equation (2).