Javascript实现Java的HashMap(链表散列)

简介: 前言如果你研究过Java中HashMap的源码,你就会知道HashMap底层的存储结构。Java中的HashMap是以链表散列的形式存储的,也就是数组+链表:HashMap中有一个Entry数组,默认的数组长度是16。

前言

如果你研究过Java中HashMap的源码,你就会知道HashMap底层的存储结构。Java中的HashMap是以链表散列的形式存储的,也就是数组+链表:HashMap中有一个Entry数组,默认的数组长度是16。这个值必须是2的整数次幂,以保证在通过key的hash值来计算entry应该放置的数组下标时可以尽量做到平均分配。而Entry数组中的每一个非空Entry都是一个Entry链表的头结点。这样做的好处就是HashMap结合了数组在寻址(查找)上的优势和链表在放置和删除上的优势。当一个链表的长度过长,查询所耗费的时间也在增加,当达到一定阈值的时候,Entry数组就会自动扩容至原来的两倍。这个时候就需要把原数组的所有元素都拷贝至新数组中,这也是HashMap操作过程中一个消耗相对大一些的操作。HashMap的存储结构如下图:


这里写图片描述

不过在JavaScript中,并没有为我们提供一个类似于HashMap的结构用于存储数据。JavaScript中的数组其实可以被用来当做一个映射集,比如如下语句

var a = new Array(1,2,3);
    a[-10]="a[-10]";
    a["sss"]="sss";

都是可以正常运行的,不过有一点需要注意的是,当[]里不是非负整数的时候,该属性并没有被存放到数组中,而是作为这个数组对象的一个属性被存储进来。所以这样的赋值显然也不会改变数组的长度。当上面的语句被执行之后,如果你输出这个数组的长度,则依然会得到3。这显然不是我们想要的结果,所以我们可以参考Java中的HashMap源码来写一个在JavaScript中适用的HashMap。

项目下载地址

正文

在Javascript中,我们仍然以”数组+链表“的链表散列形式来存储HashMap中的数据。这里我们规定key的值必须为字符串,可以为空字符串,但是不能为null或undefined。这样做的原因一是大部分的时间我们都会以字符串作为key,而我们的HashMap计算hash值的方法就是通过计算key值字符串每个字符的ASCII码并拼接获得的;还有一个原因就是Javascript中并不会像Java语言中会为每个不同的对象生成不同的hash值,所以Javascript中对象之间的比较也非常复杂。如果实现了这一功能,在put操作比较key的时候就会非常耗时,违背了HashMap设计的初衷。而对于value的类型并没有限制,可以是任何类型的变量。还有一点值得一提的是,由于Javascript数组本身就不是定容的,即可以通过赋值语句动态的增减数组的长度,所以相对于Java中的HashMap来说,我们将要实现的HashMap在扩容的时候还省去了把原数组中的entry拷贝至新数组的步骤。
下面上代码:

function HashMap(){

    //初始大小
    var size = 0;

    //数组
    var table = [];

    //初始数组长度为16
    var length = 2 << 3;

    //数组扩容临界值为12
    var threshold = 0.75 * length;

    //hash值计算
    this.hash = function(h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    //返回HashMap的size
    this.size = function(){
        return size;
    }

    //是否包含某个key
    this.containsKey = function(key) {
        if(key == null || key == undefined)
            return false;
        else {
            var hashCode = this.hashCode(key);
            var hash = this.hash(hashCode);
            var index = this.indexFor(hash, length)
            for(var e = table[index]; e != null && e != undefined; e = e.next){
                if(e.key === key){
                    return true;
                }
            }
            return false;
        }
    }

    //是否包含某个value
    this.containsValue = function(value) {
        for(var index = 0; index < table.length; index++) {
            for (var e = table[index]; e != null && e != undefined; e = e.next) {
                if (JSON.stringify(e.value) === JSON.stringify(value)) {
                    return true;
                }
            }
        }
        return false;
    }

    //HashMap是否为空
    this.isEmpty = function(){
        return size === 0;
    }

    //计算HashCode值,不同的key有不同的HashCode,这里使用字符串转ASCII码并拼接的方式
    this.hashCode = function(key){
        var hashcode = '';
        for(var i=0 ;i< key.length; i++){
            hashcode += key.charCodeAt(i);
        }
        return hashcode;
    }

    //向HashMap中存放值
    this.put = function(key, value){
        if(key == null || key == undefined)
            return
        var hashCode = this.hashCode(key);
        var hash = this.hash(hashCode);
        var index = this.indexFor(hash, length)
        for(var e = table[index]; e != null && e != undefined; e = e.next){
            if(e.key === key){
                var oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        this.addEntry(key, value, index)
    }

    //从HashMap中获取值
    this.get = function(key){
        if(key == null || key == undefined)
            return undefined
        var hashCode = this.hashCode(key);
        var hash = this.hash(hashCode);
        var index = this.indexFor(hash, length)
        for(var e = table[index]; e != null && e != undefined; e = e.next){
            if(e.key === key){
                return e.value;
            }
        }
        return undefined;
    }

    //从HashMap中删除值
    this.remove = function(key){
        if(key == null || key == undefined)
            return undefined
        var hashCode = this.hashCode(key);
        var hash = this.hash(hashCode);
        var index = this.indexFor(hash, length)
        var prev = table[index];
        var e = prev;
        while(e != null && e!= undefined){
            var next = e.next;
            if(e.key === key){
                size--;
                if(prev == e){
                    table[index] = next;
                }
                else{
                    prev.next = next;
                }
                return e;
            }
            prev = e;
            e = next;
        }
        return e == null||e == undefined? undefined: e.value;
    }

    //清空HashMap
    this.clear = function() {
        table = [];
        // 设置size为0
        size = 0;
        length = 2 << 3;
        threshold = 0.75 * length;
    }

    //根据hash值获取数据应该存放到数组的哪个桶(下标)中
    this.indexFor = function(h, length) {
        return h & (length-1);
    }

    //添加一个新的桶来保存key和value
    this.addEntry = function(key, value, bucketIndex) {
        // 保存对应table的值
        var e = table[bucketIndex];
        // 然后用新的桶套住旧的桶,链表
        table[bucketIndex] = { key: key, value: value, next: e}
        // 如果当前size大于等于阈值
        if (size++ >= threshold)
        // 调整容量
        {
            length = length << 1;
            threshold = 0.75 * length;
        }
    }

    //获取HashMap中所有的键值对
    this.getEntries = function(){
        var entries = [];
        for(var index = 0; index < table.length; index++) {
            for (var e = table[index]; e != null && e != undefined; e = e.next) {
                entries.push({key: e.key, value: e.value})
            }
        }
        return entries;
    }

}

其中hashcode这个函数,就是把key值的每个字符转换成ASCII码并且拼接的过程。这样可以保证当key值不同的时候,生成的字符串肯定也不相同。而hash这个函数则与Java中的HashMap源码中的hash方法完全相同。通过得到的这个hash值与数组的当前长度进行与运算,获取到我们要put的键值对应该放置在数组的哪个下标之中。
我们可以观察containsValue这个函数,这个函数的作用是判断HashMap中是否有某个value。在这个函数的实现里,有一个对象之间的比较:

if (JSON.stringify(e.value) === JSON.stringify(value)) {
    return true;
}

这里使用了JSON对象转字符串并进行比较,对嵌套的对象结构依然有效,不过比较的效率相对来说很低。不过相对于key的比较,value的比较并不会经常被调用,这也解释了之前所说的key只能为字符串,而value可以使任何形式的对象的说法。getEntries函数可以获得HashMap中所有的键值对,这个函数返回一个包含所有键值对的数组,如果想对HashMap进行遍历,那么可以调用这个函数,并且遍历返回的数组就可以了。

测试

测试语句如下:

 var hs = new HashMap();
    hs.put('asd', 123)
    hs.put('bqwe', 456)
    hs.put('czx', 789)
    hs.put('dcv', {a: 1, b: 2})
    hs.put('edf', 123)
    hs.put('fsdf', 456)
    hs.put('gdf', 789)
    hs.put('hds', {a: 1, b: 2})
    hs.put('idc', 123)
    hs.put('jdf', 456)
    hs.put('ker', 789)
    hs.put('lsd', [1, 2, 3])
    hs.put('mvr', {a: 1, b: 2, c: {d: 2}})
    hs.put("vvv", null)
    hs.put('', 'asdasd')
    console.log(hs.get(''))
    console.log(hs.get("qqq"))

    console.log(hs.containsKey('asd'))
    console.log(hs.get('asd'))

    hs.remove('asd')
    console.log(hs.containsKey('asd'))

    console.log(hs.containsValue({a: 1, b: 2, c: {d: 2}}))
    console.log(hs.containsValue(123))

    console.log(hs.get('asd'))
    console.log(hs.size())
    var en = hs.getEntries();

    console.log(en)

    en.forEach((item) => {
        console.log(item.key)
        console.log(item.value)
    })

    hs.clear();
    console.log(hs.isEmpty())

输出结果:

asdasd
undefined
true
123
false
true
true
undefined
14
[Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object, Object]

asdasd
hds
Object {a: 1, b: 2}
gdf
789
jdf
456
mvr
Object {a: 1, b: 2, c: Object}
fsdf
456
dcv
Object {a: 1, b: 2}
idc
123
bqwe
456
lsd
[1, 2, 3]
czx
789
ker
789
edf
123
vvv
null
true
相关文章
|
1月前
|
JavaScript 前端开发 Java
Java和JavaScript的区别
【4月更文挑战第8天】Java和JavaScript的区别
15 1
|
1月前
|
前端开发 JavaScript Java
Java和JavaScript的应用场景有显著的不同
【4月更文挑战第8天】Java和JavaScript的应用场景有显著的不同
12 1
|
6天前
|
Web App开发 JavaScript 前端开发
《手把手教你》系列技巧篇(三十九)-java+ selenium自动化测试-JavaScript的调用执行-上篇(详解教程)
【5月更文挑战第3天】本文介绍了如何在Web自动化测试中使用JavaScript执行器(JavascriptExecutor)来完成Selenium API无法处理的任务。首先,需要将WebDriver转换为JavascriptExecutor对象,然后通过executeScript方法执行JavaScript代码。示例用法包括设置JS代码字符串并调用executeScript。文章提供了两个实战场景:一是当时间插件限制输入时,用JS去除元素的readonly属性;二是处理需滚动才能显示的元素,利用JS滚动页面。还给出了一个滚动到底部的代码示例,并提供了详细步骤和解释。
30 10
|
17天前
|
存储 安全 算法
【JAVA】HashMap扩容性能影响及优化策略
【JAVA】HashMap扩容性能影响及优化策略
|
4天前
|
存储 安全 Java
Java一分钟之-Map接口与HashMap详解
【5月更文挑战第10天】Java集合框架中的`Map`接口用于存储唯一键值对,而`HashMap`是其快速实现,基于哈希表支持高效查找、添加和删除。本文介绍了`Map`的核心方法,如`put`、`get`和`remove`,以及`HashMap`的特性:快速访问、无序和非线程安全。讨论了键的唯一性、`equals()`和`hashCode()`的正确实现以及线程安全问题。通过示例展示了基本操作和自定义键的使用,强调理解这些概念对编写健壮代码的重要性。
6 0
|
4天前
|
JavaScript 前端开发 Java
Java和Javascript互调的例子
Java和Javascript互调的例子
11 3
|
4天前
|
存储 安全 Java
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
|
5天前
|
JavaScript 前端开发 Java
《手把手教你》系列技巧篇(四十)-java+ selenium自动化测试-JavaScript的调用执行-下篇(详解教程)
【5月更文挑战第4天】本文介绍了如何使用JavaScriptExecutor在自动化测试中实现元素高亮显示。通过创建并执行JS代码,可以改变元素的样式,例如设置背景色和边框,以突出显示被操作的元素。文中提供了一个Java示例,展示了如何在Selenium中使用此方法,并附有代码截图和运行效果展示。该技术有助于跟踪和理解测试过程中的元素交互。
8 0
|
9天前
|
Java
Java为什么建议初始化HashMap的容量大小?
【5月更文挑战第3天】Java中初始化HashMap容量能提升性能。默认容量16,扩容按当前的1/2进行。预估元素数量设定合适容量可避免频繁扩容,减少性能损耗。过大浪费内存,过小频繁扩容,需权衡。Java 8后扩容策略调整,但核心仍是预估初始容量以优化性能。
39 1
|
15天前
|
编解码 JavaScript 前端开发
【专栏】介绍了字符串Base64编解码的基本原理和在Java、Python、C++、JavaScript及Go等编程语言中的实现示例
【4月更文挑战第29天】本文介绍了字符串Base64编解码的基本原理和在Java、Python、C++、JavaScript及Go等编程语言中的实现示例。Base64编码将24位二进制数据转换为32位可打印字符,用“=”作填充。文中展示了各语言的编码解码代码,帮助开发者理解并应用于实际项目。