I think 90% of technical interview questions result in hashtable in it. underrated wouldn't be the word I'd use.
Diving into the world of hash tables
51–60 of 107 posts
Re: Diving into the world of hash tables
#52This article explains "2-Level Hashing" which is apparently "dynamic perfect hashing." While interesting, I'm wondering how much it's actually used? Or is it just of theoretical interest?
Re: Diving into the world of hash tables
#53I think when the author says "underrated", what they mean is "I didn't realize how important this is". Hash tables are used everywhere, by everyone, for a lot of things. Maybe they don't give it enough time in school for people to realize it is the king of practical software development.
Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…
>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)"
Can you explain where exactly and why a set operation is performed? Thanks.
Re: Diving into the world of hash tables
#54I think when the author says "underrated", what they mean is "I didn't realize how important this is". Hash tables are used everywhere, by everyone, for a lot of things. Maybe they don't give it enough time in school for people to realize it is the king of practical software development.
Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…
High-level is not a synonym for interpreted, dynamic.
Re: Diving into the world of hash tables
#55It's actually sets that are underrated. All languages should come with a reference implementation. Hashtables aka Maps aka Dictionaries aka Associative arrays are just fine.
Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that. But I think you probably meant having and using set operations effectively in day to day tasks, as in "make 2 sets and do a set different operation" instead of "do a for loop on first hash check if it is in the second, then put results in an accumulator. An…
>"Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that."
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.
Re: Diving into the world of hash tables
#56Earlier quoted context omitted.
Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…
>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)" Can you explain where exactly and why a set operation is performed? Thanks.
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 "", line 1, in
NameError: name 'a' is not defined
>>> locals()['a'] = 113
>>> a
113
>>>
For example:
>>> locals()['foo-bar'] = 1
>>> locals()['foo-bar']
1
>>> foo-bar
Traceback (most recent call last):
File "", line 1, in
NameError: name 'foo' is not defined
>>>
Re: Diving into the world of hash tables
#57Earlier quoted context omitted.
Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…
>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)" Can you explain where exactly and why a set operation is performed? Thanks.
[deleted]
Re: Diving into the world of hash tables
#58Earlier quoted context omitted.
Nearly every expression in high-level languages relies on multiple hash lookups. This is part of the reason these languages are regarded as "slow." I suppose you could use a tree in place, and get reasonable performance. However the hash table's nature allows you to pretty much throw more memory at the problem in exchange for speed (though this is hardly unique to this particular data structure). For instance `a = fo…
>"For instance `a = foo.bar.baz` in Python involves 3 hash gets (local scope, foo scope, then bar scope), and a single set operation (local scope)" Can you explain where exactly and why a set operation is performed? Thanks.
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)
Re: Diving into the world of hash tables
#59Earlier quoted context omitted.
Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that. But I think you probably meant having and using set operations effectively in day to day tasks, as in "make 2 sets and do a set different operation" instead of "do a for loop on first hash check if it is in the second, then put results in an accumulator. An…
>"Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that." 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.
Ruby's standard library does this. Here's the code: https://github.com/ruby/ruby/blob/trunk/lib/set.rb
Re: Diving into the world of hash tables
#60Quick question: are there special hash functions that are optimized for use in hash tables? Or do typical hash table implementations in e.g. Python just use standard hash functions like MD5? Edit: It's 100% clear now. Thanks for the great answers everyone!
Good question! Yes. Here’s an example: http://cyan4973.github.io/xxHash/
There's also FarmHash, whose 32-bit version is 2x as fast as xxHash on little endian machines (at least according to this benchmark suite https://github.com/rurban/smhasher).