Sets are sorted from 0-9 every single time in python?! Not unordered

user_12508908 0
Viewed 398

I thought it was a coincidence at first so I wrote up a test to try it out and it's true, I ran it 1 million times and every single time the set came back ordered and sorted. This only occurs when you use integers from 0-9 as soon as an integer > 9 is inserted then any integers inserted after will not be sorted. Why is this? Also for floats it kind of sorts it but isn't right all the time, so weird I thought they were completely unordered. Any advice on why 0-9 is sorted every time would be greatly appreciated, I didn't believe it at first either so here's the code I used you can easily run it yourself and see it's true.

import random

def check_set():
    constructing = True
    s = set()
    while constructing:
        x = random.randint(0, 9)
        if x not in s: s.add(x)
        if len(s) == 10: constructing = False
    return s
def main():
    for x in range(10000):
        l = list(check_set())
        if l != [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
            print('wow')
if __name__ == '__main__':
    main()
set int sorting python
1 Answers

Those ints hash to themselves:

>>> [*map(hash, range(10))]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

When you add the numbers 0 to 9 to a set, the set makes room for at least 10 numbers (actually 32, I think). So its internal array has at least the indexes 0 to 9. And because those numbers hash to themselves, they're stored in the set's internal array at their own index (value i gets stored at index hash(i)=i). So when you iterate it, you get them sorted.

Further illustration with smaller examples:

Sets start with internal size 8, and value i wants to go to index hash(i) % 8. So if you add 0 and 8, both want to go to index 0. The one that comes first actually gets to index 0, the other has to go to some other (larger) index. Hence:

>>> {0, 8}, {8, 0}
({0, 8}, {8, 0})

If you instead add 1 and 8, then 1 wants to go to index 1 and 8 wants to go to index 0, so 8 always comes first regardless of insertion order:

>>> {1, 8}, {8, 1}
({8, 1}, {8, 1})

An example with 0 to 9:

>>> s = set()
>>> for i in 8, 9, 0, 1, 2, 3, 4, 5, 6, 7:
        s.add(i)
        print(s)

{8}    # the only element (stored at index 0)
{8, 9}    # 9 gets stored at index 1, so after 8
{8, 9, 0}    # indices 0 and 1 are already taken, so 0 goes to some higher index
{8, 9, 0, 1}    # similar
{0, 1, 2, 8, 9}    # the set internally resized and re-added all values, each
                   # value ends up at its own index (e.g., 8 goes to index 8)
{0, 1, 2, 3, 8, 9}    # 3 goes to index 3
{0, 1, 2, 3, 4, 8, 9}    # same for the rest, all go to their own index...
{0, 1, 2, 3, 4, 5, 8, 9}
{0, 1, 2, 3, 4, 5, 6, 8, 9}
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
user_126710570
Related