🔒 hw help

[icy meteor]

im wondering if linked lists are used to maintain insertion order for dictionaries?

[opaque condor]

@icy meteor

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[whole island]

the python dictionary implementation is quite complicated

it’s not done with linked lists

[edgy topaz]

no, the hash table itself is a contiguous buffer of memory, and for collisions it uses open addressing. to my knowledge linear probing

linked lists would be too slow and cause too much overhead

[grizzled pilot]

https://github.com/python/cpython/blob/main/Objects/dictobject.c if you want

[icy meteor]

oh wow thanks very much

[whole island]

https://github.com/python/cpython/blob/main/Objects/dictnotes.txt this as well

[icy meteor]

much appreciated lads

[grizzled pilot]

line 92 of the C file starts a comment that describes how insertion order is maintained, specifically

[icy meteor]

for dictnotes.txt?

[whole island]

no, dictobject.c

[icy meteor]

oh yes thank you very much

[icy meteor]

are there any sources that would state this?

or could i just find the running time of hash tables and linear linked lists and compare

[whole island]

the problem with linked lists is that theyre O(n) lookups

while a hash table is O(1)

[icy meteor]

ohh right

[edgy topaz]

this is partially true, but not the full answer. some hashmaps use linked lists for hash collision. this algorithm is called chaining

[icy meteor]

ig this is just about the hash table used by pthon dictionaries

[edgy topaz]

linked lists are slow because they have poor cache locality, require allocations for each node, and have large overhead for small values because they must store 1-2 pointers per node

[icy meteor]

thanks a lottt

[edgy topaz]

the document zerointensity linked alludes to this

https://github.com/python/cpython/blob/main/Objects/dictnotes.txt#L126

there are two places where a linkedlist might come up in a hashmap

the underlying buffer which stores the buckets and also in the chaining collision resolution algorithm, each bucket contains a linked list

for example the java hashmap does actually use a singly linked list to store buckets, https://stackoverflow.com/questions/30957699/why-does-hashmap-internally-use-linkedlist-instead-of-arraylist

[icy meteor]

ohh right

[edgy topaz]

but it's the only serious hashmap implementation i'm aware of that uses this strategy. you should basically never use linked lists unless you're implementing an lru cache or a similar structure and really, truly need it. https://stackoverflow.com/questions/34170566/bjarne-stroustrup-says-we-must-avoid-linked-lists

https://rust-unofficial.github.io/too-many-lists/index.html#an-obligatory-public-service-announcement

[icy meteor]

sweet thanks a lot this clears everything up appreacite it

[opaque condor]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.