CODEWITHSUNDEEP
javahashhashtablehash-function
Geek
Geek

Reputation: 27193

What does variable name has to do with hash functions?

Properties of a good hash function from MIT recitation:

  1. satisfies (approximately) the assumption of simple uniform hashing: each key is equally likely to hash to any of the m slots.
  2. The hash function shouldn’t bias towards particular slots does not hash similar keys to the same slot (e.g. compiler’s symbol table shouldn’t hash variables i and j to the same slot since they are used in conjunction a lot)
  3. is quick to calculate, should have O(1) runtime
  4. is deterministic. h(k) should always return the same value for a given k

Can some one explain the point 2 further . What does variable name has to do with hash functions ?

Edit: I work with Java . So if an answer contains explanation using java semantics it is okay to me .

Upvotes: 2

Views: 597

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726639

Since hash tables are often used for building lookup tables that compilers use to look up information about symbols, such as variable names and function names, a compiler scenario is used to explain the point of #2.

The authors took a pair of variable names that are very commonly found in the same program, i and j, and said that strings representing the names of these variables, "i" and "j", should not be hashed to the same slot. This makes sense, because resolving hash collisions is the part of the lookup process that most negatively influences the speed.

Upvotes: 3

Matt Ball
Matt Ball

Reputation: 359846

The bullet point suggests that compilers use something called a symbol table which is a mapping from variable name to information about that variable, implemented as a hash table.

Which is true of many compilers.

Upvotes: 2

Related Questions