Hash tables are one of the most important data structures in computer science, not only because of their excellent read and write performance π(1), but also because they provide mappings between keys and values. To implement a high-performing hash table, you need to pay attention to two key points — hash functions and conflict resolution.
The memory model
In the source code, the map structure is hmap, which is short for Hashmap:
type hmap struct {
// Number of elements. Len (map) returns this value
count int
flags uint8
// Buckets' log log_2
B uint8
// Overflow bucket approximate number
noverflow uint16
// The hash function is passed in when the key is hashed
hash0 uint32
// Points to the buckets array, which is 2^B
// If the number of elements is 0, nil
buckets unsafe.Pointer
// Buckets will be twice as long as oldbuckets
oldbuckets unsafe.Pointer
// Indicates the capacity expansion progress. Buckets whose address is smaller than this one have been migrated
nevacuate uintptr
extra *mapextra
}
Copy the codeB is the log of the lengths of the buckets array, so the lengths of the buckets array are 2^B. Buckets store keys and values, more on that later.
Buckets are a pointer to a structure
type bmap struct{
tophash [bucketCnt]uint8
}
Copy the codeBut this is just the surface structure, which is embellished at compile time, dynamically creating a new structure:
type bmap struct{
topbits [8]uint8
keys [8]keytype
elems [8]elemtype
overflow uintptr
}
Copy the codeA Bmap is a bucket. A bucket can contain up to eight keys, all of which fall into the same bucket because they are hashed into a “class” hash. In the bucket, the high 8 bits of the hash value calculated by the key are used to determine where the key falls into the bucket (a bucket has a maximum of 8 positions).
If the map’s key and value are not Pointers and the size is less than 128 bytes, the BMAP is marked as pointerless to avoid scanning the entire Hmap during GC. If bmap does not contain any Pointers, it will move overflow to extra.
type mapextra struct{
// overflow[0] contains overflow buckets for hmap.buckets.
// overflow[1] contains overflow buckets for hmap.oldbuckets.
overflow [2]*[]*bmap
// nextOverflow contains empty Overflow buckets, which are pre-allocated buckets
nextOverflow *bmap
}
Copy the codeBmap is where k-V is stored, so let’s zoom in and take a closer look at the inside of BMAP.
The figure above shows the bucket memory model, and the HOB Hash refers to the top Hash. Key /value/key/value/… It looks like this. The advantage of this is that you can omit the padding field in some cases to save memory space.
The hash function
When the program starts, it checks whether the CPU supports AES, if so, use AES Hash, otherwise use memHash. This is done in the function alginit() under the path SRC /runtime/alg.go.
Key Location process
The key is hashed to get a hash value of 64 bits, and only the last B bits are used to calculate which bucket it will fall into. Remember the B mentioned earlier? If B is equal to 5, the number of buckets is 2^5 = 32.
For example, now we have a key hash function that evaluates to the hash result:
10010111 | 000011110110110010001111001010100010010110010101010 β 01010Copy the codeUsing the last five bits, 01010, the value is 10, which is bucket number 10. This operation is actually the mod operation, but the mod operation is too expensive, so the code implementation uses bit operation instead.
Then use the high 8 bits of the hash value to find the location of the key in the bucket, which is looking for an existing key. There is no key in the bucket at first, so the new key will find the first empty space and put it in.
A bucket number is a bucket number, and a hash conflict occurs when two different keys fall into the same bucket. The conflict is resolved using a linked list: find the first empty space in the bucket from front to back. In this way, when searching for a key, the bucket is first found and then the key in the bucket is traversed.
In the figure above, we assume B = 5, so the total number of buckets is 2^5 = 32. First compute the hash of the key to be searched, use the lower 5 bits 00110, find the corresponding bucket 6, use the higher 8 bits 10010111, corresponding to decimal 151, Bucket 6 looks for the key with the topB hash value of 151 and finds slot 2, which completes the search process.
If not found in a bucket, and overflow is not empty, continue searching overflow buckets until all or all key slots are found, including all Overflow buckets.
Expansion process
The purpose of using a hash table is to find the target key quickly. However, as more keys are added to the map, the probability of key collisions increases. As the eight cells in the bucket fill up, it becomes less and less efficient to find, insert, and delete keys. Ideally, a bucket would have only one key, which would achieve O(1) efficiency, but this would consume too much space and cost too much time.
Go language uses a bucket to load eight keys. After locating a bucket, it also needs to locate the specific key, which actually uses time to replace space.
Of course, there should be a certain degree to do this, otherwise all the keys fall into the same bucket, which directly degrades into a linked list, and the efficiency of various operations is directly reduced to O(N), which is not feasible.
Therefore, there needs to be a metric to measure the situation described earlier, which is the loading factor. The Go source code defines the load factor as follows:
loadFactor := count / (2^B)
Copy the codeCount is the number of elements in the map, and 2^B is the number of buckets.
When a new key is inserted into a map, the system checks the conditions. If the conditions meet the following two conditions, the system triggers the expansion:
- The load factor exceeds the threshold, which is defined in the source code as 6.5.
- Overflow bucket number is too large: if B is less than 15, that is, the total number of buckets 2^B is less than 2^15, if overflow bucket number is more than 2^B; If B >= 15, the total number of buckets 2^B is greater than or equal to 2^15, and the overflow number is greater than 2^15.
Through assembly language, it can be found that the function in the source code corresponding to the assignment operation is mapassign, and the source code corresponding to the expansion conditions is as follows:
if! h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
}
// The load factor exceeds 6.5
func overLoadFactor(count int64, B uint8) bool {
return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<<B))
}
// They overflow too much
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B < 16 {
return noverflow >= uint16(1)<<B
}
return noverflow >= 1<<15
}
Copy the codeThe hashGrow() function doesn’t actually “move”; it just allocates the new buckets and attaches the oldbuckets to the oldbuckets field. The action to actually move buckets is in growWork(), and the action to call growWork() is in mapassign and mapDelete. They try to move buckets when inserting, modifying, or deleting keys. Check that the Oldbuckets are moved, and specifically that the Oldbuckets are nil.
Let’s look first at what the hashGrow() function does and then at how the relocation buckets actually works.
func hashGrow(t *maptype, h *hmap) {
// B+1 is equal to 2 times the space
bigger := uint8(1)
if! overLoadFactor(h.count+1, h.B) {
// Perform the same amount of memory expansion, so B stays the same
bigger = 0
h.flags |= sameSizeGrow
}
// Hang the old buckets on the bucket
oldbuckets := h.buckets
// Apply for a new bucket space
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
flags := h.flags &^ (iterator | oldIterator)
ifh.flags&iterator ! =0 {
flags |= oldIterator
}
// Commit the action for grow
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
// The move progress is 0
h.nevacuate = 0
// overflow buckets ζ°δΈΊ 0
h.noverflow = 0
ifh.extra ! =nil&& h.extra.overflow ! =nil {
// Promote current overflow buckets to the old generation.
ifh.extra.oldoverflow ! =nil {
throw("oldoverflow is not nil")
}
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
ifnextOverflow ! =nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
}
Copy the code
The following is a macro view of the changes before and after expansion through the figure.
Before capacity expansion, B is 2 and there are four buckets. Lowbits indicates the low hash value. Let’s say we ignore other buckets and focus on bucket number two. And assume that overflow is too large, triggering equal expansion (corresponding to condition 2 above).
After capacity expansion is complete, overflow Buckets disappear and keys are concentrated into one bucket, which is more compact and improves lookup efficiency.
Suppose a double capacity expansion is triggered, and the key in the old buckets is split into two new buckets after capacity expansion. One in x part, one in y part. Depending on the lowbits of the hash. In the new map, 0-3 is called X part, and 4-7 is called Y part.
What does the traversal process look like
package main
import "fmt"
func main(a) {
ageMp := make(map[string]int)
ageMp["qcrao"] = 18
for name, age := range ageMp {
fmt.Println(name, age)
}
}
Copy the codeExecute command:
go tool compile -S main.go
Copy the codeThe key lines of assembly code are:
0x00c7 00199 (main.go:8) CALL runtime.mapiterinit(SB) ... 0x0145 00325 (main.go:8) LEAQ "".. autotmp_9+128(SP), AX 0x014d 00333 (main.go:8) CALL runtime.mapiternext(SB) ...Copy the codeIn this way, the underlying function call relationship is clear about the Map iteration. The mapiterinit function is called to initialize the iterator, and the mapiternext function is looped through for map iteration.
Iterator structure definition:
type hiter struct {
key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/gc/range.go).
elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/gc/range.go).
t *maptype
h *hmap
// The bucket pointed to during initialization
buckets unsafe.Pointer // bucket ptr at hash_iter initialization time
// The bmap currently traversed
bptr *bmap // current bucket
overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive
oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive
startBucket uintptr // bucket iteration started at
offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
wrapped bool // already wrapped around from end of bucket array to beginning
B uint8
i uint8
bucket uintptr
checkBucket uintptr
}
Copy the codeMapiterinit is an initial assignment to a field in a hiter structure.
As mentioned earlier, even traversing a dead-written map produces an out-of-order result each time. Now we can take a closer look at their implementation.
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
// Which bucket to traverse from
it.startBucket = r & bucketMask(h.B)
// Which cell of the bucket to start traversing
it.offset = uint8(r >> h.B & (bucketCnt - 1))
func bucketShift(b uint8) uintptr {
// Masking the shift amount allows overflow checks to be elided.
return uintptr(1) << (b & (sys.PtrSize*8 - 1))}func bucketMask(b uint8) uintptr {
return bucketShift(b) - 1
}
Copy the codeFor example, the uintptr(1)<< H.b-1 is the uintptr(1)<< H.b-1 and the result is 3, 0000 0011 is the lower 8 bits. BucketCnt -1 = 7, the lower 8 bits is 0000 0111, move R 2 bits to the right, and phase with 7 to get a cell with numbers 0~7.
Thus, the mapiternext function will iterate from the it.startBucket cell with the it.offset number, and extract the key and value from it until it returns to the starting bucket to complete the iterate process.
The source code section is easier to read, especially after you understand the previous comments. So, I’m going to go through the entire traversal process graphically, hopefully in a way that’s easy to understand.
Suppose we have a map like the one shown below, where B = 1 starts with two buckets, and then a capacity expansion is triggered (not to go into the capacity expansion condition here, just a setting), and B becomes 2. In addition, the contents of bucket 1 are moved to the new bucket, and Bucket 1 is split into bucket 1 and bucket 3. Bucket 0 has not been moved. The oldbuckets hang on the *oldbuckets pointer, and the new buckets hang on the *buckets pointer.
At this point, we iterate over the map. Assume that startBucket = 3 and offset = 2 after initialization. Thus, the starting point of the traversal would be cell number 2 of Bucket number 3, and the following diagram is the state in which the traversal begins:
Red indicates the start position, and the sequence of bucket traversal is 3 -> 0 -> 1 -> 2.
Because bucket 3 corresponds to the old bucket 1, check whether the old bucket 1 has been moved. The judgment method is:
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > empty && h < minTopHash
}
Copy the codeIf the value of B. topash [0] is within the range of the flag value, that is, in the interval of (0,4), it indicates that it has been moved.
empty = 0
evacuatedEmpty = 1
evacuatedX = 2
evacuatedY = 3
minTopHash = 4
Copy the codeIn this case, the old Bucket number 1 has already been moved. So its topHash [0] value is in the range (0,4), so you just iterate over the new bucket number 3.
Iterating through the cells of bucket number 3 will find the first non-empty key: element E. At this point, the mapiterNext function returns, and our traversal results in a single element:
Since the returned key is not empty, the mapiterNext function continues to be called.
Iterating back from where we left off, we find elements F and G in the new Overflow Bucket 3.
Traversal result sets are thus augmented:
After traversing through the new bucket 3, the new Bucket 0 is returned. Bucket 0 corresponds to the old bucket 0. The old bucket 0 is not moved, so the traversal of the new bucket 0 is changed to traversal of the old bucket 0. Do you want to remove all the keys from bucket 0?
It’s not that simple. Recall that the old bucket 0 will split into two buckets after the move: new bucket 0 and new bucket 2. We are traversing the new bucket 0 (note that this is traversal *bucket Pointers, also known as new buckets). So, we only fetch the keys from the old bucket 0 that were assigned to the new bucket 0 after the fission.
Therefore, lowbits == 00 will enter the traversal result set:
As before, we continue through the new bucket 1 and discover that the old bucket 1 has moved, so we only need to iterate through the existing elements of the new bucket 1. The result set becomes:
To continue iterating through the new bucket 2, it comes from the old bucket 0, so you need the keys in the old bucket 0 that will be fissile into the new bucket 2, that is, the keys with lowbit == 10.
Thus, traversing the result set becomes:
Finally, when you continue traversing to the new bucket number 3, you find that all buckets have been traversed and the entire iteration is complete.
By the way, if you run into a key like math.nan (), the process is similar. The core still depends on which bucket it falls into when it is split. I just look at the lowest order of its top hash. If the lowest hash of the top hash is 0, it is allocated to X part; If it’s 1, it’s assigned to Y part. That’s how you decide whether to pull out the key and put it in the traversal result set.
The core of the map traversal is to understand that the old bucket splits into two new buckets when doubled. The traversal operation is performed according to the sequence number of the new bucket. If the old bucket does not move, the old bucket will find the key to move to the new bucket in the future.