你的位置:首页 > Java教程

[Java教程]学习Redis你必须了解的数据结构——HashMap实现


本文版权归博客园和作者吴双本人共同所有,转载和爬虫请注明原文链接博客园蜗牛 cnblogs.com\tdws .

首先提供一种获取hashCode的方法,是一种比较受欢迎的方式,该方法参照了一位园友的文章,链接在尾部给出:

 var djb2Code = function (str) {    var hash = 5381;    for (i = 0; i < str.length; i++) {      char = str.charCodeAt(i);      hash = ((hash << 5) + hash) + char; /* hash * 33 + c */    }    return hash;  }

接下来我们用js实现hashmap, hashmap是一种键值对的数据结构。意味着你可以通过key快速找到你所需要查找的值。我使用数组加上LinkedList来实现hashmap,这种方式也被称为解决hashcode冲突的分离链接法。hashmap通常具备以下几种方法:put,get,remove。put是写入和修改数据,在put数据时,首先获取key的hashcode,作为数组的索引。而数组索引对应的值则是一个linkedlist,并且linkedlist所存储的节点值,同时包含着所需存储的key和value。这样以便解决当hashcode重复冲突时,在链表中根据key名称来get查找值。 关于hashmap更多的原理,我推荐这篇文章 http://www.admin10000.com/document/3322.html 

下面直接给出实现,其中使用到LinkedList数据结构的源码,在我的这篇分享当中:http://www.cnblogs.com/tdws/p/6033209.html

 1  var djb2Code = function (str) { 2     var hash = 5381; 3     for (i = 0; i < str.length; i++) { 4       char = str.charCodeAt(i); 5       hash = ((hash << 5) + hash) + char; /* hash * 33 + c */ 6     } 7     return hash; 8   } 9  10  11  12   function HashMap() { 13     var map = []; 14     var keyValPair = function (key, value) { 15       this.key = key; 16       this.value = value; 17     } 18     this.put = function (key, value) { 19       var position = djb2Code(key); 20       if (map[position] == undefined) { 21         map[position] = new LinkedList(); 22       } 23       map[position].append(new keyValPair(key, value)); 24     }, 25     this.get = function (key) { 26       var position = djb2Code(key); 27       if (map[position] != undefined) { 28         var current = map[position].getHead(); 29         while (current.next) { 30           if (current.element.key === key) { //严格判断 31             return current.element.value; 32           } 33           current = current.next; 34         } 35         if (current.element.key === key) {//如果只有head节点,则不会进while. 还有尾节点,不会进while,这个判断必不可少 36           return current.element.value; 37         } 38       } 39       return undefined; 40     }, 41     this.remove = function (key) { 42       var position = djb2Code(key); 43       if (map[position] != undefined) { 44         var current = map[position].getHead(); 45         while (current.next) { 46           if (current.element.key === key) { 47             map[position].remove(current.element); 48             if (map[position].isEmpty()) { 49               map[position] == undefined; 50             } 51             return true; 52           } 53           current = current.next; 54         } 55         if (current.element.key === key) { 56           map[position].remove(current.element); 57           if (map[position].isEmpty()) { 58             map[position] == undefined; 59           } 60           return true; 61         } 62       } 63     } 64   } 65  66  67  68  69   //链表 70   function LinkedList() { 71     var Node = function (element) {        //新元素构造 72       this.element = element; 73       this.next = null; 74     }; 75     var length = 0; 76     var head = null; 77  78     this.append = function (element) { 79       var node = new Node(element);        //构造新的元素节点 80       var current; 81       if (head === null) {             //头节点为空时 当前结点作为头节点 82         head = node; 83       } else { 84         current = head; 85         while (current.next) {          //遍历,直到节点的next为null时停止循环,当前节点为尾节点 86           current = current.next; 87         } 88         current.next = node;            //将尾节点指向新的元素,新元素作为尾节点 89       } 90       length++;                    //更新链表长度 91     }; 92     this.removeAt = function (position) { 93       if (position > -1 && position < length) { 94         var current = head; 95         var index = 0; 96         var previous; 97         if (position == 0) { 98           head = current.next; 99         } else {100           while (index++ < position) {101             previous = current;102             current = current.next;103           }104           previous.next = current.next;105         }106         length--;107         return current.element;108       } else {109         return null;110       }111     };112     this.insert = function (position, element) {113       if (position > -1 && position <= length) {        //校验边界114         var node = new Node(element);115         current = head;116         var index = 0;117         var previous;118         if (position == 0) {                    //作为头节点,将新节点的next指向原有的头节点。119           node.next = current;120           head = node;                        //新节点赋值给头节点121         } else {122           while (index++ < position) {123             previous = current;124             current = current.next;125           }                                //遍历结束得到当前position所在的current节点,和上一个节点126           previous.next = node;                    //上一个节点的next指向新节点 新节点指向当前结点,可以参照上图来看127           node.next = current;128         }129         length++;130         return true;131       } else {132         return false;133       }134 135     };136     this.toString = function () {137       var current = head;138       var string = '';139       while (current) {140         string += ',' + current.element;141         current = current.next;142       }143       return string;144     };145     this.indexOf = function (element) {146       var current = head;147       var index = -1;148       while (current) {149         if (element === current.element) {            //从头节点开始遍历150           return index;151         }152         index++;153         current = current.next;154       }155       return -1;156     };157     this.getLength = function () {158       return length;159     };160     this.getHead = function () {161       return head;162     };163     this.isEmpty = function () {164       return length == 0;165     }166   }

参考文章:js获取hashcode  : http://www.cnblogs.com/pigtail/p/3342977.html

如果我的点滴分享对你有点滴帮助,欢迎点击下方红色按钮,我将长期输出分享。