Keywords: hash table, weak, RunLoop, hash conflict

A hash table (also called a hash table) is a data structure that accesses data stored in memory directly by key.

The key idea of hash tables is to use hash functions to map keys to buckets. To be more precise,
  1. When we insert a new key, the hash function determines which bucket the key should be assigned to and stores the key in the appropriate bucket;
  2. When we want to search for a key, the hash table uses the same hash function to find the corresponding bucket, and searches only in specific buckets.

Hash application in iOS

Weak table

The weak table uses a global HashMap nested array structure to store data. When the object (the object to which the weak pointer points) is destroyed, the array containing all the weak Pointers to this object is found from the HashMap according to the object, and then all elements in the array are set to nil.
The most important feature of weak is that when the object is destroyed, it automatically sets nil to reduce the risk of accessing wild Pointers. This is also the original intention of weak design. After the scheme design is implemented, the basic steps of setting weak pointer to nil are as follows:
  1. (dealloc) Find an array of weak Pointers to the global HashMap, based on a unique value representing the object as the key
  2. Sets all elements in the array to nil

Weak table structure and details can be refer to the following figure and links

Struct SideTable {// Spinlock_t slock; // Reference-countedhashTable RefcountMap refcnts; // weak references globallyhashTable weak_table_t weak_table; }Copy the code


Recommended reading: www.desgard.com/weak/

Runloop

There is a one-to-one correspondence between threads and runloops (child threads may not have one), and the relationship is stored in a global Dictionary. There is no RunLoop when the thread is created, and if you don’t grab it, it never will. RunLoop creation occurs at the first fetch and RunLoop destruction occurs at the end of the thread. You can only get runloops inside a thread (except for the main thread).

Recommended reading blog.ibireme.com/2015/05/18/…

other

There are many other points that use hash tables, as shown in the figure below



The advantage of the Hash

  • Advantages: Hash tables can provide fast operations.
  • Disadvantages: Hash tables are usually based on arrays and are difficult to expand once arrays are created. There is also no easy way to traverse the data items in a table in any order, such as from smallest to largest.
In summary, if the data is not traversed in order, the well can predict the size of the data volume in advance. So hash tables are unmatched in terms of speed and ease of use.

Hash Common Questions and solutions

Hash conflict

When the keyword range is much larger than the length of the hash table and the specific value of the keyword is not known in advance. Conflicts are bound to arise. In addition, when the actual value of the keyword is greater than the length of the hash table, and the table is already full of records, if a new record is inserted, not only a conflict occurs, but also an overflow occurs
  1. The open addressing approach to conflict resolution is to use a probe (probe) technique to form a probe sequence in a hash table when a conflict occurs. The sequence is searched cell by cell until the given keyword is found, or an open address is encountered (that is, the address cell is empty). (To insert, the new node to be inserted can be stored in the address cell when the open address is detected.) If an open address is detected during the search, it indicates that there is no keyword to be searched in the table, that is, the search fails.
  2. The zipper method resolves conflicts by linking all the nodes whose keywords are synonyms in a single linked list. If the selected hash table is of length M, the hash table can be defined as a group of Pointers T[0..m-1] consisting of Pointers to m heads. Any node whose hash address is I is inserted into a single linked list with a pointer T[I] as its head. The initial values of each component in T should be null Pointers. In the zipper method, the loading factor α can be greater than 1, but generally α≤1.

There are duplicate elements (Leetcode problem)

It’s basically using hash tables to look up weights
Leetcode-cn.com/problems/co…

Sum of two numbers (Leetcode problem)

Use the hash table to find in the array
Leetcode-cn.com/problems/tw…