High-quality brush topic route reference:

Github.com/youngyangya…

Github.com/chefyuan/al…

Hash table basis

A hash table, also known as a hash table, is a mapped data structure.

A hash table is a data structure that is accessed directly according to the value of a key code.

Like old three and old three of the station: someone to find old three, the front desk little sister a point, like the dog kennel is the same as the station of the old three.

In general, a hash table consists of two elements: bucket arrays and hash functions.

Buckets and bucket arrays

The hash table uses a Bucket array, which is just a normal array of size N, except that we think of each cell as a Bucket, and each Bucket cell can hold an item.

For example, if all keys are integers, we can store the entry with key as key directly in bucket unit A. To save space, free cells are set to NULL.

For example, wu Zero, Xiong Da, Wang Er, Zhang SAN, Li Si, we can put them in the corresponding position of the bucket array.

So when we look it up, we just look for the subscript of the array by its name, and that’s order one.

However, Lao SAN said, how can someone’s name always be called “Three” or “four”? At least it should be called “A Gang” or “Xiao Ming”.

So the question is, Where should we put it, Gang and Ming? They can’t just put it in the index of the bucket array.

So, that brings us to our second key element, the hash function.

The hash function

In order for the mapping to be generalized to all cases, we need to map to the location of the bucket array using the hashFunction hashFunction.

For example, some of the common names we mentioned above, Agang, Xiaoming… We’re going to map them to their buckets.

In general, the hash function maps the name to the index of the bucket array by performing a HashCode operation on the name.

Hash collision

Our ideal situation is to find the free pit through the hash calculation of each element, but the reality is often not so satisfactory, sometimes, you will find that the city in your heart has been overgrown with other people’s ivy.

Ah Gang and Xiao Ming are mapped to the same location, but this location can only accommodate one person, this is called a hash collision.

So in order to avoid hash collisions as much as possible, we need to carefully design the hash function. We want the hash function to meet the following requirements:

• It has to be consistent
• Simple calculation
• Hash addresses are evenly distributed

Hash function constructor

There are many ways to construct a hash function, as shown in the figure below. Some of these methods are known by name, but I won’t go into them for space.

Here’s a reference to the HashMap hash function:

    static final int hash(Object key) {
        int h;
        return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
    }
Copy the code

The process is as follows:

• Get a hashCode of type int using the hashCode() method
• The high 16 bits of hashCode and the low 16 bits of hashCode do an xOR operation

HashCode moves 16 bits to the right, exactly half the size of 32bit. Do xOR operations with itself (same = 0, different = 1). The idea is to mix the high and the rank of the hash, and increase the randomness of the low. And the mixed value also keeps the high characteristic.

• The 32-bit int hashCode is too large to be indexed by modulo the length of the bucket array

int index = hash & (arrays.length-1);
Copy the code

The hash function of HashMap is an excellent design that is well worth learning.

A way to handle hash conflicts

Even with the best design, hashing is inevitable.

So, what happens when you have a hash collision?

Zipper method

Gang and Ming have a conflict in the bucket, so let’s connect a small tail in the bucket group — use a linked list to store them both.

What else is there to do?

Alas, if our bucket array still has pits, we can redistribute them, which is 👇

Linear detection method

The premise of linear detection is that there are pits in the bucket array.

Common linear detection methods are:

• Open address method

The open address method is to look for the next empty hash address as soon as a conflict occurs.

Searching for the next empty hash address is called detection, common detection methods are: linear detection method, quadratic detection method, random detection method.

• Then the hash method

This method is also very simple, using different hash functions to find a hash address, until there is no conflict.

• Public overflow zone method

The public overflow area method is to create another public overflow area to store the conflicting elements.

Hash structure in Java

In Java, we have two common hash structures.

One is a HashMap, <Key, Value> Hash structure.

One is a HashSet, a collection of no repeating elements.

A collection of	The underlying implementation	Whether to order	Whether the value can be repeated	The query efficiency	Add or delete efficiency
HashMap	Array/linked list/red black tree	no	The key cannot be repeated and the value can be repeated	O(1)	O(1)
HashSet	Array/linked list/red black tree	no	Do not repeat	O(1)	O(1)

What kind of questions do you usually Hash?

Remember the number of occurrences we did earlier?

To determine whether an element has appeared in a scene, we should immediately think of hashing.

Brush the topic field

LeetCode1. The sum of two numbers is a typical example of using a hash table, which has been done before.

LeetCode242. Valid letter heterotopic words

☕ Title: 242. Valid letter heterotopic words (leetcode-cn.com/problems/va…)

❓ Difficulty: Simple

📕 description:

Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S.

Note: if each character in S and T occurs the same number of times, s and T are said to be alphabetic allographs.

Example 1:

Enter: s ="anagram", t = "nagaram"Output:true
Copy the code

Example 2:

Enter: s ="rat", t = "car"Output:false
Copy the code

💡 ideas:

Now that we’ve talked about hashing, I don’t want to write violence.

We can use HashMap to store the frequency of character occurrence, s occurrence frequency +1, t occurrence frequency, and determine whether the value of all positions of the final hash is 0.

The idea is very simple, the code is as follows:

    public boolean isAnagram(String s, String t) {
        if(s.length() ! = t.length()) {return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            map.put(sChar, map.getOrDefault(sChar, 0) + 1);
            map.put(tChar, map.getOrDefault(tChar, 0) - 1);
        }
        for (Integer v : map.values()) {
            if(v ! =0) {
                return false; }}return true;
    }
Copy the code

There is another way to use arrays as hash tables, which is said to speed things up, but I personally find it easier to understand and remember using hashMaps.

🚗 Time complexity: O(n)

🏠 Space complexity: O(n)

LeetCode1002. Find common characters

☕ Title: 1002. Find common characters (leetcode-cn.com/problems/fi…)

❓ Difficulty: Simple

📕 description:

Given an array of strings A consisting of only lower-case letters, return A list of all characters (including repeated characters) displayed in each string in the list. For example, if a character appears three times in each string, but not four times, you need to include that character three times in the final answer.

You can return the answers in any order.

Example 1:

Input:"bella"."label"."roller"] output: ["e"."l"."l"]
Copy the code

Example 2:

Input:"cool"."lock"."cook"] output: ["c"."o"]
Copy the code

LeetCode349. Intersection of two arrays

☕ Title: 349. Intersection of two arrays (leetcode-cn.com/problems/in…)

❓ Difficulty: Simple

📕 description:

Given two arrays, write a function to calculate their intersection.

Example 1:

Enter: nums1 = [1.2.2.1], nums2 = [2.2] output: [2]
Copy the code

Example 2:

Enter: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [9.4]
Copy the code

💡 ideas:

Notice that you have to subtract the intersection. Since we are talking about de-weighting, we naturally think of HashSet.

We can use two hashsets, set1 to store nums1 elements, and set2 to traverse nums2 to determine if elements exist in set1.

It’s easy to understand.

The code is as follows:

    public int[] intersection(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if (len1 == 0 || len2 == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int i = 0; i < len1; i++) {
            set1.add(nums1[i]);
        }
        for (int j = 0; j < len2; j++) {
            if(set1.contains(nums2[j])) { set2.add(nums2[j]); }}int[] result = new int[set1.size()];
        int k = 0;
        for (int value : set2) {
            result[k++] = value;
        }
        return result;
    }
Copy the code

🚗 Time complexity: O(n)

🏠 Space complexity: O(n)

LeetCode454. Addition of four numbers II

☕ Title: 454. Adding four numbers II (leetcode-cn.com/problems/4s…)

❓ Difficulty: medium

📕 description:

Given four arraylists A, B, C, D that contain integers, calculate how many tuples (I, j, k, L) there are such that A[I] + B[j] + C[k] + D[L] = 0.

To keep things simple, all A, B, C, and D have the same length N, and 0 ≤ N ≤ 500. All integers range from -228 to 228-1, and the final result does not exceed 231-1.

Such as:

Input: A = [1.2]
B = [-2, -1]
C = [-1.2]
D = [ 0.2] output:2Explanation: The two tuples are as follows:1. (0.0.0.1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2(-) +1) + 2 = 0
2. (1.1.0.0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1(-) +1) + 0 = 0

Copy the code

💡 ideas:

The idea is that there are two groups of four numbers, one of which stores a HashMap and the other compares it with a HashMap.

• Define A HashMap where key is the sum of A and B and value is the number of occurrences of the sum of A and B.
• Iterate over the large A and large B arrays, count the sum of the two arrays, and the number of occurrences, and put them in the map.
• Int count (a+b+c+d = 0);
• Find the number of key occurrences in the map using res if 0-(C+D) occurs in the map
• Finally, return the statistic count

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sumAB = nums1[i] + nums2[j];
                map.put(sumAB, map.getOrDefault(sumAB, 0) + 1); }}for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sumCD = -(nums3[i] + nums4[j]);
                if(map.containsKey(sumCD)) { res+=map.get(sumCD); }}}return res;
    }
Copy the code

🚗 Time complexity: O(n²)

🏠 Space complexity: O(n)

LeetCode383. Ransom letter

☕ Title: 454. Adding four numbers II (leetcode-cn.com/problems/4s…)

❓ Difficulty: Simple

📕 description:

Given a ransom string and a magazine string, determine whether the first string ransom can be formed from characters in the second string magazines. Returns true if it can be formed; Otherwise return false.

In order not to reveal the handwriting of the ransom letter, search the magazine for the letters needed to form a word to express the meaning. Each character in the magazine string can only be used once in the ransom string.

Example 1:

Enter: ransomNote ="a", magazine = "b"Output:false
Copy the code

Example 2:

Enter: ransomNote ="aa", magazine = "ab"Output:false
Copy the code

Example 3:

Enter: ransomNote ="aa", magazine = "aab"Output:true
Copy the code

💡 ideas

This is also a very similar solution.

Use HashMap to store newspaper array characters and the number of characters appearing, traverse the ransom array, take the corresponding characters.

Note that each character can only be used once, so you need to subtract one from the character.

The code is as follows:

    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            char m = magazine.charAt(i);
            hash.put(m, hash.getOrDefault(m, 0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            char r = ransomNote.charAt(i);
            if(! hash.containsKey(r)) {return false;
            }
            if (hash.get(r) == 0) {
                return false;
            }
            hash.put(r, hash.get(r) - 1);
        }
        return true;
    }
Copy the code

🚗 Time complexity: O(n)

🏠 Space complexity: O(n)

LeetCode202. Happy

☕ Title: 202. Happiness number (leetcode-cn.com/problems/ha…)

❓ Difficulty: Simple

📕 description:

Write an algorithm to determine whether a number n is a happy number.

Happiness number is defined as:

• For a positive integer, replace the number each time with the sum of squares of the numbers at each of its positions.
• And then you repeat the process until the number is 1, or it could go on forever but it never gets to 1.
• If you can change it to 1, then that number is happiness.

Return true if n is the happy number; If not, return false.

Example 1:

Input:19Output:trueExplanation:12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Copy the code

Example 2:

Enter n =2Output:false
Copy the code

💡 ideas:

The key to this problem is that it could go on forever but never change to 1.

We certainly can’t make it take happy numbers in an infinite loop, but if it does, the sum of squares of the numbers must repeat, and that becomes the problem of determining whether the elements are present.

We can use HashSet to store the sum of squares. If the current sum of squares has already occurred, an infinite loop has started.

    public boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    while (true) {
        int sum = getSum(n);
        / / happy
        if (sum == 1) {
            return true;
        }
        / / the sum
        if (set.contains(sum)) {
            return false;
        } else{ set.add(sum); } n = sum; }}/ * * *@return int
     * @Description: Gets the sum of squares *@date2021/8/11 22:41 * /
    int getSum(int n) {
        int sum = 0;
        while (n > 0) {
            int temp = n % 10;
            sum += temp * temp;
            n = n / 10;
        }
        return sum;
    }
Copy the code

🚗 Time complexity: O(logn)

🏠 Space complexity: O(logn)

You can also do this in a two-pointer way, where you have two numbers, one fast, one slow, and if you go through the loop, eventually the two Pointers will meet.

conclusion

Or a catchphrase:

Do simple things repeatedly, do repetitive things seriously, do serious things creatively!

I am three points evil, a full stack of literary and military development.

Like, pay attention to not get lost, let’s see you next time!

---

Reference:

[1]. Github.com/youngyangya…

[2]. Github.com/chefyuan/al…

[3]. Data Structures and Algorithms

[4]. Discussion on hash algorithm in HashMap

[5]. Interview brush algorithm, these API must know!

[6]. Leetcode-cn.com/problems/4s…