Hash table and Hash map in javascript

Question

Internal representation of a hashtable && hashmap is,

In Java, hashtable and hashmap is differentiated in terms of synchronous/asynchronous operation, otherwise internal representation is same.

Javascript object literal notation,

var obj = {
           e1: 1,
           e2: 2,
           e3: 3  
         };

can be directly used as hashtable and hashmap with its internal hashing function. Object literal has string or Symbols as keys.

ES6 has also introduced window.Map with any value as keys.

1) Does the above internal representation for hashtable and hashmap, looks correct? (or) Is there a difference in internal represenation of hashtable and hashmap?

2) Does Javascript object literal provide O(1) computation for hashtable/hashmap without any collision?

Answer 1

Your picture is one way to implement a hash table data structure - there are others. Your image is an example of "separate chaining", "open addressing" is another common strategy. As of Java 7 both Hashtable and HashMap used a form of chaining (look at their Entry classes), however Java 8 introduced a massive rewrite of HashMap (but not Hashtable, as it's a legacy class) to use a tree structure rather than a linked list for its chains. The point being the exact algorithm used by both classes is an implementation detail and is subject to change between releases.

"HashMap" and "Hashtable" are just class names defined by the JDK, they do not necessarily correspond to particular hashing algorithms. JavaScript does not have separate "HashMap" and "Hashtable" concepts, because they don't need them. Java needed to create a separate HashMap class because the Hashtable contract was problematic and couldn't be safely corrected.

So, to answer your questions:

1) Sort-of; it does not properly represent Java 8's HashMap, but it's conceptually not far off. Hashtable does still use this algorithm, but you should almost never use Hashtable.

2) Like you say, JavaScript objects use a hash table data structure under the covers. This does (generally) provide O(1) field access, but like any hash table implementation it must deal with the possibility of conflicts. As discussed in the question @overexchange linked to the exact implementation is browser-dependent.