Dictionaries and Hash

2018-03-20

Dictionaries

  • Creating a dictionary in ES5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function Dictionary(){
    var items = {};
    this.set = function(key, value){
        items[key] = value;
    }
    this.delete = function(key){
        if (this.has(key)){
            delete items[key];
            return true;
        }
        return false;

    }
    this.has = function(key){
        //return key in items;   
        // it will return true if the key is on items' prototype
        return items.hasOwnProperty(key);
    }
    this.get = function(key){
        return this.has(key) ? items[key] : undefined;
    }
    this.clear = function(){
        items = {};
    }
    this.size = function(){
        return Object.keys(items).length;
    }
    this.keys = function(){
        return Object.keys(items);
    }
    this.values = function(){
        var values = [];
        for (var k in items){
            if(this.has(k)){
                values.push(items[k]);
            }
        }
        return values;

    }
    this.getItems = function(){
        return items;
    }

}

The Hash Table

  • Hashing consists of finding a value in a data structure in the shortest time possible.
  • A hash function is a function that, given a key, will return an address in the table where the value is.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

function HashTable() {
    var table = {};
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        table[position] = value;
    }
    this.remove = function(key){
        table[loseloseHashCode(key)] = undefined;
    }
    this.get = function(key){
        reture table[loseloseHashCode(key)];
    }

    var loseloseHashCode = function (key) {
        var hash = 0;
        for (var i = 0; i < key.length; i ++){
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
}
``` 

## Handling Collisions between hash tables

- Separate Chaining
    - Creating a linked list for each position of the table and storing the elements in it

```javascript

var ValuePair = function(key, value){
    this.key = key;
    this.value = value;

    this.toString = function(){
        return '[' + this.key + ' - ' + this.value + ']';
    }
}

function HashTable() {
    var table = {};
    this.put = function(key, value){
        var position = loseloseHashCode(key);

        if(table[position] == undefined){
            table[position] = new LinkedList();
        }
        table[position].append(new ValuePair(key, value));
    }
    this.get = function(key){
        var position = loseloseHashCode(key);

        if (table[position] !== undefined){
            var current = table[position].getHead();

            while(current.next){
                if( current.element.key === key ){
                    return current.element.value;
                }
                current = current.next;
            }

            if(current.element.key === key){ // check in case first or last element
                return current.element.value;
            }
        }
        return undefined;
    }
    this.remove = function(key){
        var position = loseloseHashCode(key);

        if (table[position] !== undefined){
            var current = table[position].getHead();
            while( current.next ){
                if (current.element.key === key){
                    table[position].remove(current.element);
                    if (table[position].isEmpty()){
                       table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;            
            }
            if (current.element.key === key){
                table[position].remove(current.element);
                if (table[position].isEmpty()){
                    table[position] = undefined;
                }
                return true;
            }
        }
        return false;
    }

    var loseloseHashCode = function (key) {
        var hash = 0;
        for(var i = 0; i < key.length; i++){
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
}
  • Linear Probing
    • When we try to add a new element, if the position is already occupied, then we will try index + 1. if index + 1 is occupied, then we will try index + 2 and so on.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
function HashTable (){
    var table = [];
    this.put = function(key, value){
        var position = loseloseHashCode(key);

        if (table[position] == undefined) {
            table[position] = new ValuePair(key, value);
        } else {
            var index = ++ position;
            while( table[index] != undefined){
                index ++;
            }
            table[index] = new ValuePair(key, value);
        }
    }
    this.get = function(key){
        var position = loseloseHashCode(key);

        if (table[position] !== undefined){
            if (table[position].key === key){
                return table[position].value;
            } else {
                var index = ++position;
                while (table[index] === undefined 
                || table[index].key !== key){
                    index ++;
                }
                if (table[index].key === key){
                    return table[index].value;
                }
            }
        }
        return undefined;
    }
    this.remove = function(){
        var position = loseloseHashCode(key);
        if (table[position] !== undefined){
            table[position] = undefined;
        } else {
            var index = ++position;
            while( table[index] === undefined
            || table[index].key !== key){
                index ++;
            }
            if (table[index].key === key){
                table[index] = undefined;
            }
        }
    }
    var loseloseHashCode = function(key){
        var hash;
        for (var i=0; i < key.length; i++){
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    }
}

Creating better hash functions

  • The previous hash function has too many collisions.
  • A good hash function should require less time to insert and retrieve an element and have low probalibity of collisions.
1
2
3
4
5
6
7
var djb2HashCode = function(key) {
    var hash = 5381;
    for (var i = 0; i < key.length; i++){
        hash = hash * 33 + key.charCodeAt(i);
    }
    return hash % 1013;
}

The ES6 Map class

  • ES6 has the naive implement of the Map class.

    The ES6 Weakmap and Weakset classes

  • The only difference between the Map or Set classes and their Weak versions are:

    • The WeakSet or WeakMap classes do not have the entries, keys and vlaues. Thus, there is no way to retrieve a value unless you know the key object.
    • Only Objects can work as a key.