If i ever see a list of tuples or "key value pair" as a substitute for dictionary or hash map or whatever im going to go crazy

  • 4
    there's valid use cases. like if you want the ability of multiple values for a single key.
  • 2
    Oy, don't disrespect Prolog maps like that.
  • 1
    Isn't that what the implementation of a dictionary resolves to or is it more binary treeish ?
  • 0
    I have to resist the urge to play a song right now fearful that's it's stuck in my head because I already played it
  • 1
    @AvatarOfKaine a list<keyvaluepair> would be a terrible implementation of a dictionary.


    "Retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey,TValue> class is implemented as a hash table."
  • 0
    @tosensei oh i wish thats why its used in my case
  • 0
    @tosensei spooky. Yesterday I was thinking about that topic and wondered if I should ask on devrant.

    I’m wondering how dictionaries or hashmaps are implemented. How can it access a random element in constant time without reserving a huge amount of space?

    I know the theory like the hashing of the key and then looking into the bucket that corresponds to that hash.
    But how is that bucket found in constant time? Wouldn’t it need to iterate over all buckets to find the correct hash? How is it not O(n)?

    It’s not of any use for me, I’d just like to know.
  • 1
    @Lensflare the hash is an int and the "buckets" are an array. So what happens is object hash % array length = the position of the object in the HashTable. This is of course overly simplified but the underlying principle is more or less that. There are of course other implementations as well, but this is the one most learn at the beginning
  • 0
    @Lensflare if its stored in a memory registry 0x0000dfc210e , and that memory address is what the hash function evaluates to, you can directly access the value without needing to iterate over anything
  • 0
    @FallingUpwards but when a new entry is inserted, the length of the array will change and the old locations become invalid.
  • 1
    @bioDan I thought about that but surely you can’t just use some random memory location to store the values of a dictionary. You would risk accessing something else.
  • 1
    @Lensflare the memory range is usually in the free memory scope of the available RAM for the running application unless its otherwise explicitly defined.
  • 0
    Well, lists of tuples are a pretty simple way to implement an ordered or unordered map. For small sets of key-value-pairs, lookup and manipulation can even be faster than when having to calculate a hash first. Also, a naive implementation can be better than a complex one just because it is less complex and therefore easier to verify to be correct for all cases.
  • 0
    @bioDan I still don’t see how that would work.
    What if you have multiple dictionaries? They would point to the same location in memory for equal keys.
    That would imply that dict1["key"] and dict2["key"] always point to the same value. But it’s not the case.

    Also, that would require each dictionary to reserve 2^32 (or more, depending on the hash size) memory slots. That’s too large and it’s obviously not what is happening.
  • 0
    The R in RAM.
    Every variable in your program will have its own range in memory randomly allocated. There is no problem in implementing what you say.

    Unused addresses will be clear by the garbage collector or you will run out of memory. No need to reserve 3^32 space since the address will be randomly allocated based on free memory in RAM.

    So depending on the programming language implementation, if you do
    dict1["key"] = 'hi';
    dict1["key"] = 'bye';

    will either
    1. Change the value in the memory address or
    2. Will assign a new memory address with the value and the old memory address will be cleared by the garbage collector.
  • 0
    @bioDan let’s say I do this
    dict1["key1"] = "value1"

    According to your explanation, the implementation will calculate a hash of "key1", some 32 bit integer like 1234.
    Now 1234 can be used directly as an address in memory, or maybe it needs to be transformed, idk. Let’s assume it will be transformed to the memory address 5678. Now the implementation needs to check if this location is free. If it’s not free, then what? Assign a different address? Based on what? And if a different address is used, how will it be found again, when I try to access the value in the dict?
    var myValue = dict1["key1"]

    I think it is not relevant if the memory is managed by a GC or not.
    But if it is, let’s assume C (manual memory management).
  • 0
    @tosensei why not just use a hashmap of key to list of values
  • 2
    @cultab because, in those very few use cases where you actually _want_ a list of KVPs, anything more complex would be overkill.
Add Comment