“This is the 8th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Where there is life, there is learning

digression

Big year early 3, everybody have to see the Spring Festival file, say “this killer is not too calm” return quite good look of, but, today the film ticket of the Spring Festival file how so expensive, how to return a responsibility, my money is the wind blows of, conscience won’t pain of!

Without further ado, load up

LeetcCode-3

The oldest string without repeating characters

The title is as follows:

Given a strings, please find the one that does not contain repeated charactersThe eldest son ofThe length of the.

This is the same problem, because we still have knowledge

Go implementation algorithm

func lengthOfLongestSubstring(s string) int {
	strmap := make(map[byte]int)

	count := 0
	for i, j := 0.0; j < len(s); j++ {
		if val, ok := strmap[s[j]]; ok {
			i = max(val, i)
		}
		count = max(count, j-i+1)
		strmap[s[j]] = j + 1   // Add elements
	}
	return count
}

func max(x, y int) int {
	if x > y {
		return x
	} else {
		return y
	}
}
Copy the code

Review of minor issues

Quick question: What is a load factor? What do load factors do? What is the capacity expansion mechanism?

The previous two sessions have basically clarified the core definition and storage structure of map underlying structure, so today we will talk about the expansion mechanism of Map

Map hash conflict. Procedure

When it comes to the expansion of map, it is certain to mention the hash conflict handling of map. Actually, the last two times have more or less mentioned the hash conflict.

The hash conflict of a map means that two or more keys are hash computed and allocated to the same bucket.

Each bucket has a capacity of eight key-value pairs, so when multiple identical keys are thrown into the same bucket and the bucket is not large enough, go will use the link address approach, that is, * overflow points to the next bucket, connecting the buckets in a linked list manner.

The specific structure is similar to the following.

Map load factor

When it comes to capacity expansion and hash conflicts, there is another indispensable mechanism, load factor.

The Map in Java also has a load factor, which is 0.75 by default, triggering expansion whenever the hash bucket capacity reaches the maximum capacity of the load factor * hash.

Although there is no explicit definition in the GO map, there is a similar formula code as follows

This might not make sense, but there’s no context, so I’ll just say it

Load factor = number of keys/number of bucketsCopy the code

For example, if there are 8 buckets and 8 key-value pairs, the load factor of the hash table is 1

The load factor represents a hash table conflict, and for the load factor,

If the load factor is too small, the space usage is low. If the load factor is too large, serious conflicts occur and the access efficiency is lowCopy the code

Only when the load factor is in an appropriate range can the overall map efficiency be high

The mechanism in GO is that rehash is triggered when the load factor reaches 6.5

Map capacity expansion mechanism

Map expansion is progressive and varies according to different scenarios. Generally, map expansion can be triggered in two scenarios

When the load factor is greater than 6.5, an average of 6.5 key-value pairs are stored per bucket. Overflow number > 2^15, that is, overflow number exceeds 32768.Copy the code

The first method usually triggers incremental capacity expansion by creating a new bucket twice the length of the original bucket and moving the data from the old bucket to the new bucket.

To prevent delay caused by moving a large amount of data already stored, Go adopts a stepwise move strategy, that is, each time a map is accessed, a move is triggered, and two key-value pairs are moved each time.

The second method generally triggers equal expansion. For example, in extreme scenarios, the data in the map is constantly added and deleted, but the key-value pairs are concentrated in a small number of buckets. This will cause the overflow bucket number to increase, but the load factor is not high enough to perform incremental migration

An equal expansion does not create a new bucket, but rather rearranges the loose key-value pairs in the same way that a rehash is triggered to make the bucket more used and thus faster access.

You thought it was over

Small question: We are going to have a new question, surprise or not, surprise or not, that’s it. Merges two ordered lists

We’ll talk about it in the next one, so stay tuned

After reading, you find any mistakes, write them down below! Rub it in with my Black Tiger Fu!