iosswiftdictionarynsdictionaryordereddictionary

Reputation: 4075

Swift - Stored values order is completely changed in Dictionary

I tried to display datas which is in Dictionary format. Below, three attempts are there. First attempt, output order is completely changed. Second attempt, output order is same as input. But, in third attempt, I declared variable as NSDictionary. Exact output I received. Why this changes in Dictionary? Kindly guide me. I searched for Swift's Dictionary tag. But I couldn't found out.

//First Attempt
var dict : Dictionary = ["name1" : "Loy", "name2" : "Roy"]
        println(dict)

//output:
[name2: Roy, name1: Loy]

//Second Attempt
var dict : Dictionary = ["name2" : "Loy", "name1" : "Roy"]
        println(dict)

//output:
[name2: Loy, name1: Roy]
-----------------------------------------------------------

//Third Attempt With NSDictionary
var dict : NSDictionary = ["name1" : "Loy", "name2" : "Roy"]
            println(dict)

//output:
{
    name1 = Loy;
    name2 = Roy;
}

ANOTHER QUERY: I have used play ground to verify. My screen shot is below:

play_ground_screen_shot

Here, In NSDictionary, I gave name5 as first, but in right side name2 is displaying, then, in println, it is displaying in ascending order. Why this is happening??

play_ground_screen_shot_2

Here, In Dictionary, I gave name5 as first, but in right side name2 is displaying, then, in println, it is displaying, how it is taken on the Dictionary line. Why this is happening??

Upvotes: 32

Answers (8)

Mojtaba Hosseini

Reputation: 119458

✅ It is possible!

Although the Dictionary is not ordered, you can make it preserve the initial order by using the official OrderedDictionary from the original Swift Repo

The ordered collections currently contain:

Ordered Dictionary (That you are looking for)
Ordered Set

_{They said it is going to be merged in the Swift's source code soon (reference WWDC21)}

Upvotes: 4

grego

Reputation: 512

Dictionaries, by nature, are not designed to be ordered, meaning that they're not supposed to be (although they can be!).

From the Dictionaries (Swift Standard Library documentation):

A dictionary is a type of hash table, providing fast access to the entries it contains. Each entry in the table is identified using its key, which is a hashable type such as a string or number. You use that key to retrieve the corresponding value, which can be any object. In other languages, similar data types are known as hashes or associated arrays.

This requires some basic knowledge of Data Structures, which I'll outline & oversimplify briefly.

Storing associated data without a dictionary

Consider for a minute if there was no Dictionary and you had to use an array of tuples instead, to store some information about different fruits and their colors, as another answer suggested:

let array = [
   ("Apple", "Red"),
   ("Banana", "Yellow"),
   // ...
]

If you wanted to find the color of a fruit you'd have to loop through each element and check its value for the fruit, then return the color portion.

Dictionaries optimize their storage using hash functions to store their data using a unique hash that represents the key that is being stored. For swift this means turning our key—in this case a String—into an Int. Swift uses Int-based hashes, which we know because we all read the Hashable protocol documentation and we see that Hashable defines a hashValue property that returns an Int.

Storing associated data with a dictionary

The benefits of using a dictionary are that you get fast read access and fast write access to data; it makes "looking up" associated data easy and quick. Typically O(1) time complexity, although the apple docs don't specify, maybe because it depends on the key type's hash function implementation.

let dictionary = [
  "Apple": "Red",
  "Banana": "Yellow"
  // ...
]

The trade off is that the order is typically not guaranteed to be preserved. Not guaranteed means that you might get lucky and it might be the same order, but it's not intended to be, so don't rely on it.

As an arbitrary example, maybe the string "Banana" gets hashed into the number 0, and "Apple" becomes 4. Since we now have an Int we could, under the hood, represent our dictionary as an array of size 5:

// what things *might* look like under, the hood, not our actual code
// comments represent the array index numbers
let privateArrayImplementationOfDictionary = [
  "Yellow",  // 0
  nil,       // 1
  nil,       // 2
  nil,       // 3
  "Red",     // 4
]            // count = 5

You'll notice, we've converted our keys into array indices, and there are a bunch of blank spaces where we have nothing. Since we are using an array, we can insert data lightning fast, and retrieve it just as quickly.

Those nil spaces are reserved for more values that may come later, but this is also why when we try to get values out of a dictionary, they might be nil. So when we decide to add more values, something like:

dictionary["Lime"] = "Green"        // pretend hashValue: 2
dictionary["Dragonfruit"] = "Pink"  // pretend hashValue: 1

Our dictionary, under the hood, may look like this:

// what things *might* look like under, the hood, not our actual code
// comments represent the array index numbers
let privateArrayImplementationOfDictionary = [
  "Yellow",  // 0 ("Banana")
  "Pink",    // 1 ("Dragonfruit")
  "Green",   // 2 ("Lime")
  nil,       // 3 (unused space)
  "Red",     // 4 ("Apple")
]            // count = 5

As you can see, the values are not stored at all in the order we entered them. In fact, the keys aren't even really there. This is because the hash function has change our keys into something else, a set of Int values that give us valid array indices for our actual storage mechanism, an array, which is hidden from the world.

I'm sure that was more information than you wanted and probably riddled with many inaccuracies, but it gives you the gist of how a dictionary works in practice and hopefully sounds better than, "that's just how it works."

When searching for the actual performance of Swift dictionaries, Is Swift dictionary ... indexed for performance? ... StackOverflow had some extra possible relevant details to offer.

If you're still interested to know more details about this, you can try implementing your own dictionary as an academic exercise. I'd also suggest picking up a book on Data Structures and Algorithms, there are many to choose from, unfortunately I don't have any suggestions for you.

The deeper you get into this topic the more you'll understand why you'll want to use one particular data structure over another.

Hope that helps!

Upvotes: 5

Bug Hunter Zoro

Reputation: 1915

A little late for the party but if you want to maintain the order then use KeyValuePairs, the trade-off here is that if you use KeyValuePairs you lose the capability of maintaining unique elements in your list

var user: KeyValuePairs<String, String> {
    return ["FirstName": "NSDumb",
            "Address": "some address value here",
            "Age":"30"]
}

prints

["FirstName": "NSDumb", "Address": "some address value", "Age": "30"]

Upvotes: 9

Schemetrical

Reputation: 5536

This is because of the definition of Dictionaries:

Dictionary

A dictionary stores associations between keys of the same type and values of the same type in an collection with no defined ordering.

There is no order, they might come out differently than they were put in.
This is comparable to NSSet.

Edit:

NSDictionary

Dictionaries Collect Key-Value Pairs. Rather than simply maintaining an ordered or unordered collection of objects, an NSDictionary stores objects against given keys, which can then be used for retrieval.

There is also no order, however there is sorting on print for debugging purposes.

Upvotes: 23

Leo Dabus

Reputation: 236380

You can't sort a dictionary but you can sort its keys and loop through them as follow:

let myDictionary = ["name1" : "Loy", "name2" : "Roy", "name3" : "Tim", "name4" : "Steve"]   // ["name1": "Loy", "name2": "Roy", "name3": "Tim", "name4": "Steve"]


let sorted = myDictionary.sorted {$0.key < $1.key}  // or {$0.value < $1.value} to sort using the dictionary values
print(sorted) // "[(key: "name1", value: "Loy"), (key: "name2", value: "Roy"), (key: "name3", value: "Tim"), (key: "name4", value: "Steve")]\n"
for element in sorted {
    print("Key = \(element.key) Value = \(element.value)" )
}

Upvotes: 16

Antoine

Reputation: 23996

This is indeed an issue with dictionaries. However, there's a library available to make sure the order stays the way you initialised it.

OrderedDictionary is a lightweight implementation of an ordered dictionary data structure in Swift.

The OrderedDictionary structure is an immutable generic collection which combines the features of Dictionary and Array from the Swift standard library. Like Dictionary it stores key-value pairs and maps each key to a value. Like Array it stores those pairs sorted and accessible by a zero-based integer index.

Check it out here: https://github.com/lukaskubanek/OrderedDictionary

Upvotes: 0

Greg Parker

Reputation: 8012

Neither NSDictionary nor Swift::Dictionary orders its storage. The difference is that some NSDictionary objects sort their output when printing and Swift::Dictionary does not.

From the documentation of -[NSDictionary description]:

If each key in the dictionary is an NSString object, the entries are listed in ascending order by key, otherwise the order in which the entries are listed is undefined. This property is intended to produce readable output for debugging purposes, not for serializing data.

Upvotes: 2