JavaScript实现的HashTable（键值对）类

wawor4827 发布于2019-08-19 17:20 / 2193人阅读

摘要：原生中同样也没有实现的数据类型注意是类型，并不是结构，有与它类似的数据结构，的其实本质上就是一种的形式，他可以看做是一种的数据结构。下面，我会用到的特性来实现这种数据类型。所以综合考虑后，编写了正文实现中的代码。

引言

在后端语言中存在HashTable数据结构，他可以以一种key/value的形式保存数据，同时也可以通过key快速获取value的值。这是一种很便捷也很常用的功能。
原生JS中同样也没有实现HashTable的数据类型（注意是类型，并不是结构），有与它类似的数据结构——Object，JS的Object其实本质上就是一种key/value的形式，他可以看做是一种HashTable的数据结构。
下面，我会用到Object的特性来实现HashTable这种数据类型。

实现

//trim方法借鉴jQuery
var whitespace = "[x20	
f]",
    rtrim = new RegExp("^" + whitespace + "+|((?:^|[^])(?:.)*)" + whitespace + "+$", "g");
//直接在string的原型上做了扩展
String.prototype.trim = String.prototype.trim || function () {
    return this.treplace(rtrim, "");
};

//HashTable实现
function HashTable() {
    var self = this,
        hash = {},
        count = 0,
        keys = [],
        values = [];
    self.checkKey = function (key) {
        if ((typeof key === "string" && key.trim !== "") || typeof key === "number" || typeof key === "boolean") {
            return key;
        } else {
            /*本来想实现一个key也可以是复杂类型（如Object）的了，但是考虑下，
            实际开发中，复杂类型当做key的情况并不多，而且如果实现，可能会影响
            现在这种利用object特性快速取值的方式，影响性能；故限制key采取必须是
            基本类型的方式。*/
            throw new Error("Key必须是一个存在值的基本类型，并且值不可为空");
        }
    };
    self.add = function (key, value) {
        key = this.checkKey(key);
        hash[key] = value;//保证key唯一，重复key，value会被覆盖
        count++;
        if (keys.indexOf(key) == -1) {
            keys.push(key);
        }
        if (values.indexOf(value) == -1) {
            values.push(value);
        }
        return self;
    };
    self.remove = function (key) {
        key = this.checkKey(key);
        if (hash.hasOwnProperty(key)) {
            var value = hash[key];
            delete hash[key];
            count--;
            if (count < 0) {
                count = 0;
            }
            var kIndex = keys.indexOf(key),
                vIndex = values.indexOf(value);
            if (kIndex != -1) {
                keys.splice(kIndex, 1);
            }
            if (vIndex != -1) {
                values.splice(vIndex, 1);
            }
        }
        return self;
    };
    self.clear = function () {
        for (var i = 0; i < keys.length; i++) {
            if (hash.hasOwnProperty(keys[i])) {
                delete hash[keys[i]];
            }
        }
        keys.splice(0, keys.length);
        values.splice(0, values.length);
        return self;
    };
    self.count = function () {
        return count;
    };
    self.contains = function (key) {
        return keys.indexOf(key) !== -1;;
    };
    self.containsKey = function (key) {
        return keys.indexOf(key) !== -1;
    };
    self.containsValue = function (value) {
        return values.indexOf(value) !== -1;
    };
    self.getKeys = function () {
        return keys.concat([]);
    };
    self.getValues = function () {
        return values.concat([]);
    };
    //根据key获取值
    self.getValue = function (key) {
        if (hash.hasOwnProperty(key)) {
            return hash[key];
        }
    };
    //提供快捷遍历函数
    self.each = function (fun) {
        if (typeof fun === "function") {
            for (var i = 0; i < keys.length; i++) {
                var key = keys[i],
                    value = hash[key];
                var stop = fun.call({
                    key: key,
                    value: value
                }, key, value);
                if (stop === false) break;
            }
        }
    };
    self.toList = function () {
        var result = [];
        for (var i = 0; i < keys.length; i++) {
            var key = keys[i],
                value = hash[key];
            result.push({
                key: key,
                value: value
            });
        }
        return result;
    };
};

改进

第一版实现中，我是在add方法中，直接将key加载了HashTable这个类的实例上的，这样做的好处是：可以更接近类似的后端使用方式，如下：

var ht = new HashTable();
ht.add("key1","value1");
ht["key2"]="value2";
ht.getValue("key2");//value2
ht["key1"];//value1

这样的实现会在使用时提供更大便捷，但是数据有效性不能保证，如：如果key是HashTable实例的一个方法名，那就有可能被覆盖，方法会失灵。
所以综合考虑后，编写了正文【实现】中的代码。
如果大家有更好的实现方式也可以分享，大家一起学习~~

服务器托管海外云主机 js获取json数据的键值对 js键值对的值的数据类型键值对 redis键值对

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/78423.html

Map总结，看这篇就够了

摘要：继承于，实现了接口。的定义的定义从中，我们可以看出和都实现了接口。指向的的总的大小是迭代器还是枚举类的标志为，表示它是迭代器否则，是枚举类。默认加载因子指定容量大小的构造函数当的实际容量阈值时，阈值总的容量加载因子，就将的容量翻倍。概要学完了Map的全部内容，我们再回头开开Map的框架图。showImg(https://segmentfault.com/img/remote/146...

yzzz 2019-08-15 17:49 评论0 收藏0
Hashtable源码分析_JDK1.8版本

摘要：简介声明文章均为本人技术笔记，转载请注明出处声明和一样也是散列表，存储元素也是键值对继承于类类声明了操作键值对的接口方法，实现接口定义键值对接口大部分类用修饰，证明是线程安全的基本数据结构键值对数组，每个本质上是一个单向链表的表头阈值装填因 Hashtable简介声明文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yzwall Hashta...

tunny 2019-08-14 18:04 评论0 收藏0
Java 集合Hashtable源码深入解析

摘要：分别获取正序反序的键集。是用来实现机制的第部分源码解析基于为了更了解的原理，下面对源码代码作出分析。实现了迭代器和枚举两个接口获取的迭代器若的实际大小为则返回空迭代器对象否则，返回正常的的对象。概要前面，我们已经系统的对List进行了学习。接下来，我们先学习Map，然后再学习Set；因为Set的实现类都是基于Map来实现的(如，HashSet是通过HashMap实现的，TreeSe...

Turbo 2019-08-15 17:49 评论0 收藏0
站在巨人肩膀上看源码-Map

摘要：在学习的实现类是基于实现的前，先来介绍下接口及其下的子接口先看下的架构图如上图是映射接口，中存储的内容是键值对。是继承于的接口。中的内容是排序的键值对，排序的方法是通过比较器。 Map 在学习Set(Set的实现类是基于Map实现的)、HashMap、TreeMap前，先来介绍下Map接口及其下的子接口.先看下Map的架构图:showImg(https://segmentfault.c...

xiaotianyi 2019-08-15 18:06 评论0 收藏0
js数据结构和算法（五）字典和散列（hash）

摘要：哈希表也是种数据结构，它可以提供快速的插入操作和查找操作。一个更好的散列函数为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数，这和计算散列值时使用的取余运算有关。散列函数将学生里的数字相加，使用函数计算出散列值。什么是字典结构？字典是以键值对形式存储数据的数据结构，就像电话号码薄里的名字和电话号码那样的一一对应的关系。 javascript的Object类就是以...

Hegel_Gu 2019-08-21 10:23 评论0 收藏0