IT工程師數位筆記本

      function Dictionary() {
        var items={};
        this.set=function (key,value) {
          items[key]=value;
        };
        this.remove=function (key) {
          if(this.has(key)){
            delete items[key];
            return true;
          }
          return false;
        };
        this.has=function (key) {
          return key in items;
        };
        this.get=function(key){
          return this.has(key)?items[key]:undefined;
        };
        this.clear=function(){

        };
        this.size=function(){

        };
        this.keys=function () {

        };
        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;
        };

      }
      // 解決散列值重復的三種方法：分離鏈接、線性探查、雙散列法。
      // 1、分離鏈接法為散列表的每一個位置創建一個鏈表并將元素存儲在里面
      //分離鏈接的哈希表
      //被注釋的為普通的哈希表
      function HashTable() {
        var table=[];
        var loseHashCode=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=loseHashCode(key);
          // console.log(position,"-",key);
          // table[position]=value;
          if(table[position]==undefined){
            //每一個位置都是一個鏈表
            table[position]=new LinkedList();
          }
          table[position].append(new ValuePair(key,value));
        };
        this.remove=function(key){
          //table[loseHashCode(key)]=undefined;
          var position=loseHashCode(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(element);
              if(table[position].isEmpty()){
                table[position]=undefined;
              }
              return true;
            }
          }
          return false;
        };
        this.get=function(key){
          //return table[loseHashCode(key)];
          var position=loseHashCode(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) {
              return current.element.value;
            }
          }
          return undefined;
        };
        this.print=function(){
          for (var i = 0; i < table.length; i++) {
            if(table[i]!=undefined){
              console.log(i,":",table[i]);
            }
          }
        };
      }
      //2、線性探查
      // 當想向表中某個位置加入一個新的元素時，如果索引為index的位置已經被占據了，
      // 就嘗試index+1的位置。如果index+1的位置也被占據了，就嘗試index+2的位置
      // 以此類推
      function LDHashTable() {
        // ... 省略重復的代碼
        this.put=function (key,value) {
          if(table[position]==undefined){
            table[position]=new KeyValuePair(key,value);
          }else{
            var index=++position;
            while (table[index]!=undefined) {
              index++
            }
            table[position]=new KeyValuePair(key,value);
          }
        }
        this.get=function (key) {
          var position=loseHashCode(key);
          if(table[position]!==undefined){
            if(table[position].key===key){
              return table[position].value;
            }else{
              var index=++index;
              // 原書中是 table[index]===undefined || table[index].key!==key
              while (table[index]!==undefined && table[index].key!==key) {
                index++;
              }
              if(table[index] && table[index].key===key){
                return table[index].value;
              }
            }
          }
        }
      }

      // 更好的散列函數
      var djb2HashCode=function (key) {
        var hash=5381;//一個質數，大多數情況下為5381
        for (var i = 0; i < key.length; i++) {
          hash=hash*33+key.charCodeAt(i);
        }
        return hash%1013;//1013為比散列表大小要大的一個質數
      }