Null's Blog

Javascript中的hashtable

今天跟一个搞java后端的同学聊面试的问题。他说,他接到一个公司的电话面试,其中有个问题是,用没用过hashtable,我同说学说用过,之后,面试官又问,hashtable的应用场景,我同学当然也是答的上来,最后,面试官问hashtable在jdk里是如何实现的。。。然后,这个问题就没有然后了。
我想了一下,hashtable无论在什么语言里,实现思路应该各有不同,比如在java或.net里,key是放在一个超大的数组里的,当然可能是经过某个算法转换后的key值,然后在get的时候,也是根据参数转换后快速读取到数组的某个位置,并且在新增之前判断key是否存在。
思路并不复杂,就想了想javascript的实现方式。由于javascript的特殊性,不一定要使用数组的方式去存储hashtable,可以直接使用Object,并且Javascript本身提供遍历对象属性的方法,那这就容易很多了。
一般的hashtable都有几个重要的方法吧,比如:

  • length,读取hashtable的key数量
  • set(key,value),增加key、value的方法,key为字符串类型,可能要加入判断是否已均在这个key了,如果存在,java与.net中的做法为抛出异常,而这里javascript的实现可以是修改那个key对应的value值
  • get(key),读取key对应的value值
  • remove(key),删除一个key和其对应的value值
  • contains(key),判断是否存在特定的key,该方法可以不对外开放。
  • clear,清空这个hashtable
  • forEach,支持hashtable的遍历 能想到的方法和信息就包含这些,思路已清晰,实现起来就容易了:
    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
    "use strict"
    ;(function (root, factory) {
    if (typeof define === 'function' && define.amd) {
    define([], factory);
    }else if(typeof exports === 'object') {
    module.exports = factory();
    }else{
    root.store = factory();
    }
    }(this, function () {
    var HashTable = {
    length:0,
    obj:{}
    };
    HashTable.get = function(key){
    return this.obj[key];
    };
    HashTable.set = function(key,value){
    if(this.obj.hasOwnProperty(key)){
    this.obj[key] = value;
    return false;
    }else{
    this.obj[key] = value;
    this.length = this.length + 1;
    return true;
    }
    };
    HashTable.contains = function(key){
    if(this.obj.hasOwnProperty(key)){
    return true;
    }else{
    return false;
    }
    };
    HashTable.remove = function(key){
    if(this.obj.hasOwnProperty(key)){
    this.length = this.length - 1;
    }
    delete this.obj[key];
    };
    HashTable.clear = function(){
    this.obj = {};
    this.length = 0;
    };
    HashTable.forEach = function(callback){
    for(var key in this.obj){
    callback&&callback(key,this.obj[key]);
    }
    }
    window.HashTable = HashTable;
    return HashTable;
    }));