The author soliloquized: When an interviewer asked me about the underlying implementation principle of NSDictionary, I was only able to use it when I was developing. How could I know the internal implementation principle of NSDictionary? I looked so confused that I felt quite different from the interviewer. Really understanding is good for you, never say I’m going to run out, that’s just a junior dev requirement right? Without further ado, I hope you will pay attention.

In a nutshell: NSDictionary uses hash tables to map and store keys and values in OC.

So the question is what is a hash table?

Hash table: Also known as a hash table, is a data structure that is directly accessed based on key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping is called a function, and the array of records is called a hash table.

The key takeaway from reading this is that a hash table is an array, and each element in the array is called a bin, which holds key-value pairs. Take a look at a schematic diagram:

Hash stored procedures are described as follows:

  1. Calculate its hash value h based on the key value;
  2. If the number of boxes is n, then the key-value pair should be in the (h%n) box.
  3. If the bin already has key-value pairs, use either open addressing or zipper to resolve the conflict. When using the zipper method to resolve hash collisions, each bin is actually a linked list in which all key-value pairs belonging to the same bin are arranged.

Based on this, we conclude that the dictionary in OC is actually an array, and each element in the array is also an array implemented by a linked list, that is, an array within an array.

So how are dictionaries stored in oc?

When each object is created in OC, a hashCode is generated by default, that is, a string of numbers generated by the hash algorithm. When key is used to fetch the value in the dictionary, traversal or binary search is relatively inefficient. The hashCode generated for each key is then used to place the key-value pair in the hasCode array at a specified location, so that when the key is used for the value, there is no need to traverse to obtain it, and the hashCode can be directly retrieved. Because hashCode is too large, you might have to mod to a smaller number, but if you mod 999, the result will always be between 0 and 999. The downside of this, however, is that the values you get from the mod may be the same, which may result in completely unrelated key-value pairs being overwritten by new key-value pairs whose values are the same after the mod, resulting in an array of nested list implementations within an array. In this way, the key-value pairs with the same value obtained from the remainder of the key value are stored in the same linked list array. When searching for the value corresponding to the key, first obtain the linked list array, and then iterate through the number group to obtain the correct value corresponding to the key.

At this point, the underlying principle of NSDictionary is basically thoroughly explained, and I hope there is some enlightenment for those who see it, so the author is satisfied.