JavaScript-Data-Structures-and-Alo/HashCollisionLinearProbing.html at master · cqA7/JavaScript-Data-Structures-and-Alo · GitHub

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
104
105
106
107
108
109
110
111
112
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>HashCollisionLinearProbing</title>
</head>
<body>
<script>
    function HashP() {

        let table = [];

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

        //散列函数
        let loseloseHashCode = function (key) {
            let hash = 0;
            for (let i = 0; i < key.length; i++) {
                hash += key.charCodeAt(i);
            }
            return hash % 37;
        };

        let hashCode = function (key) {
            return loseloseHashCode(key);
        };

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

        this.get = function (key) {
            let position = hashCode(key);
            if (table[position] !== undefined) {
                if (table[position].key === key) {
                    return table[position].value;
                } else {
                    let index = ++position;
                    while (table[index] !== undefined && (table[index] && table[index].key !== key)) {
                        index++;
                    }
                    if ((table[index] && table[index].key === key)) {
                        return table[index].value;
                    }
                }
            } else {
                return undefined;
            }
        };

        this.remove = function (key) {
            let position = hashCode(key);
            if(table[position] !== undefined){
                if(table[position].key === key){
                    table[position] = undefined;
                    return true;
                }else {
                    let index = ++position;
                    while (table[index] !== undefined &&(table[index]&&table[index].key !== key)){
                        index++;
                    }
                    if((table[index]&&table[index].key === key)){
                        table[index] = undefined;
                        return true;
                    }
                }
            }else {
                return false;
            }
        };

        this.print = function () {
            for (let i = 0; i < table.length; ++i) {
                if (table[i] !== undefined) {
                    console.log(i+'----'+table[i].toString());
                }
            }
        };
    }

    let hashp = new HashP();
    hashp.put('Gandalf', 'gandalf@email.com');
    hashp.put('John', 'johnsnow@email.com');
    hashp.put('Tyrion', 'tyrion@email.com');
    hashp.put('Aaron', 'aaron@email.com');
    hashp.put('Donnie', 'donnie@email.com');
    hashp.put('Ana', 'ana@email.com');
    hashp.print();
    console.log("*********************");
    console.log(hashp.get("Aaron"));
    console.log("*********************");
    hashp.remove("Tyrion");
    hashp.print();
    console.log("*********************");
    console.log(hashp.get("Aaron"));//There is a Bug...

</script>
</body>
</html>