Hash数据结构

HashMap

实现原理

image.png

hashmap是由数组和链表共同组成的,数组的特点是插入慢读取快,链表的特点是插入快读取慢,hashmap结合两者优势,插入读取速度快。
先介绍一下Entry,Entry包括key、value、hash、next。
在put过程中,首先计算key的hash值,再根据hash及数组长度,算出当前key、value属于数组中的哪个元素,若此位置中没有元素则直接插入,若有元素则先根据hash值及key的值是否相等来决定是否替换当前已存在的value,若相等则替换,若不相等则将put的key、value放入当前数组中,并将原来的值作为next放入Entry中。
若key为null,则将此元素放置在数组的首位置,即table[0]。
get比较简单,通过key的hash和值来判断,先在数组中寻找,接着通过循环数组中的链表,不断获取Entry的next寻找,直接返回匹配的value。

HashMap不是同步的

HashSet

HashSet内部实现的是HashMap,其构造函数如下:

public HashSet() {
        map = new HashMap<>();
    }

add:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

remove:

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

contains:

public boolean contains(Object o) {
    return map.containsKey(o);
}

HashTable

HashTable和HashMap差不多
不同点:
1、HashMap继承AbstractMap,HashTable继承Dictionary
2、HashMap允许key,value为null,HashTable不允许
3、HashMap线程不安全,HashTable安全,内部方法是synchronized,可多个线程使用

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。