Is set ordered in python?

Set - is a collection in which elements have no order. In other words, the order is not guaranteed, but the order in which they are displayed (during iteration) is not random either, and knowing the implementation details, one can make assumptions about the order in which they will be output.

So why are the elements sorted in our case? In a set, elements are not arranged in a random order but in ascending order of the hash value modulo the length of the list. How does a set work? Internally, we have the same list, and we also want to retrieve elements by index (because it’s fast). But how do we obtain the index?

We take the hash(element) to get the hash value of the element, which is an integer. As we have previously determined, hash(int) -> int. Next, to obtain the index, we take the remainder of dividing this hash value by the length (the actual length, not the filled length) of the list inside the set.

When we declare an empty set, the default length is 8.

In other words, if we declare such a set, it will be stored roughly in the following form: s = {2, 3, 1, 5}

s = {2, 3, 1, 5}
# [NULL, 1, 2, 3, NULL, 5, NULL, NULL]
# 2 - hash(2) = 2, 2 % 8 = 2 (index in the list)
# 3 - hash(3) = 3, 3 % 8 = 3 (index in the list)
# 1 - hash(1) = 1, 1 % 8 = 1 (index in the list)
# 5 - hash(5) = 5, 5 % 8 = 5 (index in the list)

To convert the set to a list, we need to iterate through all the indexes and retrieve the non-NULL values from there. Thus, we have:

list(s) == [1, 2, 3, 5] # True

This only works with numbers that are smaller than the length of the list. For example s = {2, 3, 1, 8}

s = {2, 3, 1, 8}
# [8, 1, 2, 3, NULL, NULL, NULL, NULL]
2 - hash(2) = 2, 2 % 8 = 2 (index in the list)
3 - hash(3) = 3, 3 % 8 = 3 (index in the list)
1 - hash(1) = 1, 1 % 8 = 1 (index in the list)
8 - hash(8) = 8, 8 % 8 = 0 (index in the list)
list(s) == [1, 2, 3, 8] # now False

Never rely on the order in sets. This code is purely for example and explanation purposes. The initial size of the set (the list under the hood) is 8, but as soon as we fill 2/3 of the 8 elements, the size increases fourfold, to be precise. Fourfold — if the number of elements in the set is less than 50,000. Twofold — if it’s greater than 50,000.

All these parameters and numbers may change in the future.