Here is a review of the iOS common collection class implementation, mainly the following:

  • NSMutableSet
  • NSMutableDictionary
  • NSMutableArray
  • NSOrderedSet

NSMutableSet & NSMutableDictionary

These are both hash tables, nothing special. The average set/get operation is O(1).

Two common ways to handle hash conflicts are open addressing and chained addressing.

Take a look at the underlying implementation of note-set NSSet and dictionary NSDictionary

NSMutableArray

NSMutableArray is not a simple array, you can refer to [NSMutableArray principle to expose] (blog) joyingx) me / 2015/05/03 /… Principle revealed /)

It uses a ring buffer in its implementation to achieve a structure similar to a two-way queue.

Let’s use an example of inserting data at the beginning:

As shown, we have an NSMutableArray of [B,C,D,E], where the actual storage structure may be [B,C,D,E, NULL, NULL], and the ring buffer starts at index 0 in the actual storage. If you want to insert object A at 0, it will actually insert object A at index 5. The storage structure becomes [B,C,D,E, NULL,A], and the ring buffer starts at index 5 in the actual storage.

This makes NSArray O(1) insertion efficiency at the beginning and end, whereas normal arrays are O(N) insertion efficiency at the beginning.

NSOrderedSet

I didn’t find any data, but I could have saved an NSSet plus an NSArray, right? Update both indexes separately when data is updated.

About the hash

NSObject has a property: @ Property (readonly) NSUInteger hash; Hash tables such as NSSet/NSDictionary use this property to determine whether two objects are consistent, and by default, it is the object’s memory address (see). But if the object can be modified, and you really want to de-weight not by memory address but by content, then manually implement the hash and isEqual methods.