Diving into the world of hash tables

I think you might be a little confused. Even in hash tables with chaining, one does not tend to spend much time traversing linked lists, because the typical bucket will have only one member. This depends on the load factor of the table, but most practical implementations will eventually rebucket and rehash if their load factor grows too high. "Getting the key loaded" -- i.e. finding the memory location that contains the key -- is O(1) on average in all practical hash tables. It does not typically require any traversal at all.

You keep on talking about ordered tables like red black trees, as in this comment, which is another sign that makes me wonder if you might be confused.

> You can implement the sorted vector of keys with a hash function instead of a coindexed vector of values

So you're saying you're going to hash the keys, then sort them according to the hash, with tie breaking on the key itself? I'm not aware of any sorted table that does this, but I'm sure some exist. I suppose you'd get something of a win if N was large, and the keys had long common prefixes, and you didn't care about the ordering property.

But in that case you'd probably use an actual hash table, not the algorithm you just described. Unless there's something I'm missing.

It's often true due to a few factors. One is that they are safe, whereas a specific use case may not need the same level of safety. They generally optimize for the general case as well, but in your own code you can optimize for the very specific use case you have. One I ran into many years ago was implementing my own singly linked list by adding the next pointer to another piece of data. In this one specific case it was worth removing another layer of indirection. I was still young though, so there were probably even better ways of handling it.

I have only encountered these scenarios a small handful of times, but I'm not a very low level developer.

> In fact, what performance oriented devs need to be taught about these days is how to not use hash tables, or, more generally, dictionaries. They are a super-easy data structure to reach for, but often it is possible to arrange your data such that their use is unnecessary.

A lot of devs are completely unaware of what's happening at the layer of abstraction below them and this is one of the ways that comes out. The number of elements it takes before hash tables are faster than iterating through an array can be surprisingly large and yet it's one of the first "optimizations" that get made.

Some other related problems are not knowing how expensive network calls are, not knowing what the ORM is doing, caching in memory even though the database already is and more. They just don't think about performance issues in code they don't write.

Are you serious that dictionaries are a problem for performance oriented developers?

Performance oriented devs should be concerned with bottlenecks, not incredibly minute details. There's almost no situation I can think of where smallish dictionaries are much better or worse than any other data structure when it comes to performance.

Of course, if you're writing a compiler then it can be a serious difference. Most developers don't write compilers though.

99.999% of projects are not going to have any meaningful hot path in variable resolution.

If your program is sensitive to that, even a simple GC pause is going to destroy your performance and you need to be out of managed memory languages at that point.

There are a lot of reasons python can be slow, but this is far from one of them.

> Well, I'm not an expert in this, but at a high level, each variable is assigned a location in memory or registers, and then future references to that variable are rewritten to refer to the memory location by register name or memory address. This takes the whole "looking up a name" issue out of the path of work that has to get done at runtime.

Python does this for local variable names in functions. Because of this, moving a tight loop from global scope to a function can make it a couple percent faster.

When the name `a` is assigned the value of `baz`, Python is setting a key name `a` in the local dictionary (hash table) `locals()`.

Basically `a = 1` is syntactic sugar for `locals()['a'] = 1`

  >>> a
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  NameError: name 'a' is not defined
  >>> locals()['a'] = 113
  >>> a
  113
  >>>

One interesting side-effect of this is you can assign names that are not valid Python syntax explicitly.

For example:

  >>> locals()['foo-bar'] = 1
  >>> locals()['foo-bar']
  1
  >>> foo-bar
  Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
  NameError: name 'foo' is not defined
  >>> 

The name `foo-bar` can't be literally referenced, because the interpreter attempts to interpret it as the subtraction operation `foo - bar`.

Since Python is an interpreter, it keeps a dictionary/hash table of the local and global variables. These can be accesses by the functions `locals()` and `globals()`.

`a = ... ` can be thought of as `locals()["a"] = ...`

(although you can should not actually modify the local variables this way)

It's easier if you look at the bytecode produced for the expression, which is:

    1           0 LOAD_NAME                0 (foo)
                2 LOAD_ATTR                1 (bar)
                4 LOAD_ATTR                2 (baz)
                6 STORE_NAME               3 (a)
                8 LOAD_CONST               0 (None)
               10 RETURN_VALUE

The CPython implementation is a stack-based virtual machine. The first instruction here, LOAD_NAME, pushes co_names['foo'] (basically, whatever 'foo' is bound to in local scope) to the top of the stack. That's at least one hash table lookup, since the scope is a hash table mapping names to values. Then LOAD_ATTR replaces the top-of-stack value with the value of its 'bar' attribute. That's another hash table lookup, since attributes are a hash table mapping names to values. Then another LOAD_ATTR to get to 'baz', that's another hash table lookup. Then STORE_NAME binds the value at the top of the stack to the name given as an argument ('a'). That's an insert or update of a hash table.

So, the expression 'a = foo.bar.baz' involves at least three hash table lookups and one insert or update.

That's because it is the hash tables.

You can have dynamic binding (assuming that's what you meant, dynamic linking is something else) with way fewer hash lookups.

> While that's true you could implement one that way, it's very nice to have the set operations implemented

Unrelated, but does anyone know why the new JavaScript set implementation is so limited? Why didn't they bother doing this right?

This exactly, I hear over and over: just use a hashtable...totally misses the point.

Not in the set. You're describing the same thing as the parent comment, but you're saying "arbitrary value" which they substituted for "True"

Ruby's standard library does this. Here's the code: https://github.com/ruby/ruby/blob/trunk/lib/set.rb

Python essentially does this as well.

The idea is that an item is in the set if it's in the hash table. You can add, remove, or test for membership in constant average time.

Set operations still need to be built on top of this.

> Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks.

Sure. Np!

I mean that a simplified set is just a hash where the elements of the set are keys of the hash table and the values can be anything. I used 1 or True as example.

As in adding an element would be:

   my_dict[element] = 1

Then membership check is:

   if element in my_dict

Then removal is deleting:

   del my_dict[element]

and so on.

In other words, the reason sets are sometimes not explicitly there is because they are easy to implement on top of existing data structures.

Basic operations like union, difference, intersection between two sets can be done with a few simple for loops.

But like I mentioned in other comment, there is one interesting aspect to set (and hashes) in that the element now have to be hash-able. That kind of depends how mutability and identity works in the particular language.