用js来实现那些数据结构12（散列表）

    // 这里我们没在重复的去写clear，size等其他的方法，因为跟前面实在是没啥区别。function HashMap() {    // 我们使用数组来存储元素    var list = [];    //转换散列值得loselose散列函数。    var loseloseHashCode = function (key) {        var hash = 0;        // 遍历字符串key的长度，注意，字符串也是可以通过length来获取每一个字节的。        for(var i = 0; i < key.length; i++) {            hash += key.charCodeAt(i)        }        //对hash取余，这是为了得到一个比较小的hash值，        //但是这里取余的对象又不能太大，要注意        return hash % 37;    }    //通过loselose散列函数直接在计算出来的位置放入对应的值。    this.put = function (key,value) {        var position = loseloseHashCode(key);        console.log(position + "-" + key);        list[position] = value;    }    //同样的，我们想要得到一个值，只要通过散列函数计算出位置就可以直接拿到，无需循环    this.get = function (key) {        return list[loseloseHashCode(key)];    }    //这里要注意一下，我们的散列表是松散结构，也就是说散列表内的元素并不是每一个下标index都一定是有值，    //比如我存储两个元素，一个计算出散列值是14，一个是20，那么其余的位置仍旧是存在的，我们不能删除它，因为一旦删除，我们存储元素的位置也会改变。    //所以这里要移除一个元素，只要为其赋值为undefined就可以了。    this.remove = function (key) {        list[loseloseHashCode(key)] = undefined;    }    this.print = function () {        for(var i = 0; i < list.length; i++) {            // 大家可以把这里的判断去掉，看看到底是不是松散的数组结构。            if(list[i] !== undefined) {                console.log(i + ":" + list[i]);            }        }    }}//那么我们来测试一下我们的hashMapvar hash = new HashMap();hash.put("Gandalf",'www.gandalf.com');hash.put("John",'www.john.com');hash.put("Tyrion",'www.tyrion.com');//因为我们在put代码中加了一个console以便我们更好的理解代码，我们看一下输出// 19-Gandalf// 29-John// 16-Tyrionconsole.log(hash.get('John'));//www.john.comconsole.log(hash.get("Zaking"));//undefined//那么我们来移除一个元素Johnhash.remove("John");console.log(hash.get("John"));//undefined

var conflictHash = new HashMap();conflictHash.put("Gandalf",'www.Gandalf.com');//19-GandalfconflictHash.put("John",'www.John.com');//29-JohnconflictHash.put("Tyrion",'www.Tyrion.com');//16-TyrionconflictHash.put("Aaron",'www.Aaron.com');//16-AaronconflictHash.put("Donnie",'www.Donnie.com');//13-DonnieconflictHash.put("Ana",'www.Ana.com');//13-AnaconflictHash.put("Jonathan",'www.Jonathan.com');//5-JonathanconflictHash.put("Jamie",'www.Jamie.com');//5-JamieconflictHash.put("Sue",'www.Sue.com');//5-SueconflictHash.put("Mindy",'www.Mindy.com');//32-MindyconflictHash.put("Paul",'www.Paul.com');//32-PaulconflictHash.put("Nathan",'www.Nathan.com');//10-NathanconflictHash.print();/*5:www.Sue.com10:www.Nathan.com13:www.Ana.com16:www.Aaron.com19:www.Gandalf.com29:www.John.com32:www.Paul.com*/

function  edList() {//...链表方法}// 创建分离链接法下的hashMap。function SeparateHashMap () {    var list = [];  //loselose散列函数。    var loseloseHashCode = function (key) {        var hash = 0;        for(var i = 0; i < key.length; i++) {            hash += key.charCodeAt(i)        }        return hash % 37;    }  //这里为什么要创建一个新的用来存储键值对的构造函数？  //首先我们要知道的一点是，在分离链接下，我们元素所存储的位置实际上是在链表里面。  //而一旦在该散列位置下的链表中有多个值，我们仍旧需要通过key去找链表中所对应的元素。  //换句话说，分离链接下的存储方式是，首先通过key来计算散列值，然后把对应的key和value也就是ValuePair存入 edList。  //这就是valuePair的作用了。    var ValuePair = function (key,value) {        this.key = key;        this.value = value;        this.toString = function () {            return "[" + this.key + "-" + this.value + "]";        }    }  //同样的，我们通过loselose散列函数计算出对应key的散列值。    this.put = function (key,value) {        var position = loseloseHashCode(key);    //这里如果该位置为undefined，说明这个位置没有链表，那么我们就新建一个链表。        if(list[position] == undefined) {            list[position] = new  edList();        }    //新建之后呢，我们就通过 edList类的append方法把valuePair加入进去。    //那么如果上面的判断是false，也就是有了链表，直接跳过上面的判断执行加入操作就好了。        list[position].append(new ValuePair(key,value));    }    this.get = function (key) {        var position = loseloseHashCode(key);    //链表的操作前面相应的链表文章已经写的很清楚了。这里就尽量简单说清    //如果这个位置不是undefined，那么说明存在链表        if(list[position] !== undefined) {      //我们要拿到current，也就是链表中的第一个元素进行链表中的遍历。            var current = list[position].getHead();      //如果current.next不为null说明还有下一个            while(current.next) {        //如果要查找的key是当前链表元素的key，就返回该链表节点的value。        //这里要注意一下。current.element = ValuePair噢！                if(current.element.key === key) {                    return current.element.value;                }                current = current.next;            }      //那么这里刚开始让我有些疑惑。为啥还要单独判断一下？      //我们回头看一下，我们while循环的条件是current.next。没current什么事啊...对了。      //所以，这里我们还要单独判断一下是不是current。      //总结一下，这段get方法的代码运行方式是从第一个元素的下一个开始遍历，如果到最后还没找到，就看看是不是第一个，如果第一个也不是，那就返回undefined。没找到想要得到元素。            if(current.element.key === key) {                return current.element.value;            }        }        return undefined;    }  //这个remove方法就不说了。跟get方法一模一样，get方法是在找到对应的值的时候返回该值的value，而remove方法是在找到该值的时候，重新赋值为undefined，从而移除它。    this.remove = function (key) {        var position = loseloseHashCode(key);        if(list[position] !== undefined) {            var current = list[position].getHead();            while(current.next) {                if(current.element.key === key) {                    list[position].remove(current.element);                    if(list[position].isEmpty()) {                        list[position] = undefined;                    }                    return true;                }                current = current.next;            }             if(current.element.key === key) {                list[position].remove(current.element);                if(list[position].isEmpty()) {                    list[position] = undefined;                }                return true;            }        }        return false;    };    this.print = function () {        for(var i = 0; i < list.length; i++) {            // 大家可以把这里的判断去掉，看看到底是不是松散的数组结构。            if(list[i] !== undefined) {                console.log(i + ":" + list[i]);            }        }    }}var separateHash = new SeparateHashMap();separateHash.put("Gandalf",'www.Gandalf.com');//19-GandalfseparateHash.put("John",'www.John.com');//29-JohnseparateHash.put("Tyrion",'www.Tyrion.com');//16-TyrionseparateHash.put("Aaron",'www.Aaron.com');//16-AaronseparateHash.put("Donnie",'www.Donnie.com');//13-DonnieseparateHash.put("Ana",'www.Ana.com');//13-AnaseparateHash.put("Jonathan",'www.Jonathan.com');//5-JonathanseparateHash.put("Jamie",'www.Jamie.com');//5-JamieseparateHash.put("Sue",'www.Sue.com');//5-SueseparateHash.put("Mindy",'www.Mindy.com');//32-MindyseparateHash.put("Paul",'www.Paul.com');//32-PaulseparateHash.put("Nathan",'www.Nathan.com');//10-NathanseparateHash.print();/*5:[Jonathan-www.Jonathan.com]n[Jamie-www.Jamie.com]n[Sue-www.Sue.com]10:[Nathan-www.Nathan.com]13:[Donnie-www.Donnie.com]n[Ana-www.Ana.com]16:[Tyrion-www.Tyrion.com]n[Aaron-www.Aaron.com]19:[Gandalf-www.Gandalf.com]29:[John-www.John.com]32:[Mindy-www.Mindy.com]n[Paul-www.Paul.com]*/console.log(separateHash.get("Paul"));/*www.Paul.com*/console.log(separateHash.remove("Jonathan"));//trueseparateHash.print();/*5:[Jamie-www.Jamie.com]n[Sue-www.Sue.com]10:[Nathan-www.Nathan.com]13:[Donnie-www.Donnie.com]n[Ana-www.Ana.com]16:[Tyrion-www.Tyrion.com]n[Aaron-www.Aaron.com]19:[Gandalf-www.Gandalf.com]29:[John-www.John.com]32:[Mindy-www.Mindy.com]n[Paul-www.Paul.com]*/

function LinearHashMap () {    var list = [];    var loseloseHashCode = function (key) {        var hash = 0;        for(var i = 0; i < key.length; i++) {            hash += key.charCodeAt(i)        }        return hash % 37;    }  var ValuePair = function (key,value) {    this.key = key;    this.value = value;    this.toString = function () {      return "[" + this.key + "-" + this.value + "]";    }  }    this.put = function (key,value) {    var position = loseloseHashCode(key);      //同样的，若是没有值。就把该值存入        if(list[position] == undefined) {      list[position] = new ValuePair(key,value);    } else {      // 如果有值，那么久循环到没有值为止。      var index = ++position;      while(list[index] != undefined) {        index++      }      list[index] = new ValuePair(key,value);    }    }    this.get = function (key) {        var position = loseloseHashCode(key);    if(list[position] !== undefined) {      if(list[position].key === key) {        return list[position].value;      } else {        var index = ++position;        while(list[index] === undefined || list[index].key !== key) {          index ++;        }        if(list[index] .key === key) {          return list[index].value        }      }    }    return undefined;    }    this.remove = function (key) {        var position = loseloseHashCode(key);    if(list[position] !== undefined) {      if(list[position].key === key) {        list[index] = undefined;      } else {        var index = ++position;        while(list[index] === undefined || list[index].key !== key) {          index ++;        }        if(list[index] .key === key) {          list[index] = undefined;        }      }    }    return undefined;    };    this.print = function () {        for(var i = 0; i < list.length; i++) {            // 大家可以把这里的判断去掉，看看到底是不是松散的数组结构。            if(list[i] !== undefined) {                console.log(i + ":" + list[i]);            }        }    }}var linearHash = new LinearHashMap();linearHash.put("Gandalf",'www.Gandalf.com');//19-GandalflinearHash.put("John",'www.John.com');//29-JohnlinearHash.put("Tyrion",'www.Tyrion.com');//16-TyrionlinearHash.put("Aaron",'www.Aaron.com');//16-AaronlinearHash.put("Donnie",'www.Donnie.com');//13-DonnielinearHash.put("Ana",'www.Ana.com');//13-AnalinearHash.put("Jonathan",'www.Jonathan.com');//5-JonathanlinearHash.put("Jamie",'www.Jamie.com');//5-JamielinearHash.put("Sue",'www.Sue.com');//5-SuelinearHash.put("Mindy",'www.Mindy.com');//32-MindylinearHash.put("Paul",'www.Paul.com');//32-PaullinearHash.put("Nathan",'www.Nathan.com');//10-NathanlinearHash.print();console.log(linearHash.get("Paul"));console.log(linearHash.remove("Mindy"));linearHash.print();

var djb2HashCode = function(key) {  var hash = 5831;  for(var i = 0; i < key.length; i++) {    hash = hash * 33 + key.charCodeAt(i);  }  return hash % 1013;}