动手实现hashmap - wqybokeyuan - D1h.Net第一号博客
返回主页

wqybokeyuan

动手实现hashmap

动手实现hashmap

引入问题

为什么需要hashmap?

我已经知道的数据结构:

  • 数组
  • 链表

数组的优点:

  • 有数组下标,按下标查找快,
  • 由于存储空间连续,插入删除慢
  • 扩容不方便,容易造成空间浪费

链表的优点

  • 传入链表节点,则插入删除快,O(1)
  • 由于没有下标,必须按顺序遍历,按下标查找慢,O(n)
  • 扩容方便

我们开始思考:有什么方式既能够具备数组的 快速查询 的优点又能融合链表 方便快捷的增加删除元素 的优势?

hashmap呼之欲出。

hashmap原理

HashMap的底层主要是基于 数组链表 来实现的,它之所以有相当快的查询速度主要是因为它是通过计算 散列码 来决定存储的位置。HashMap中主要是通过key的 hashCode 来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的 hash冲突 。学过数据结构的同学都知道,解决hash冲突的方法有很多,HashMap底层是通过 链表 来解决hash冲突的。

从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点Bucket桶。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

 首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。

测试

还得用JUnit测试

(12条消息) IDEA中添加junit4的三种方法(详细步骤操作)_gakki_200的博客-CSDN博客

Map.Entry接口

 public interface Entry<K, V> { K getKey(); V getValue(); V setValue(V var1); boolean equals(Object var1); int hashCode(); static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() { return (Comparator)((Serializable)((var0x, var1x) -> { return ((Comparable)var0x.getKey()).compareTo(var1x.getKey()); })); } static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() { return (Comparator)((Serializable)((var0x, var1x) -> { return ((Comparable)var0x.getValue()).compareTo(var1x.getValue()); })); } static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> var0) { Objects.requireNonNull(var0); return (Comparator)((Serializable)((var1x, var2x) -> { return var0.compare(var1x.getKey(), var2x.getKey()); })); } static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> var0) { Objects.requireNonNull(var0); return (Comparator)((Serializable)((var1x, var2x) -> { return var0.compare(var1x.getValue(), var2x.getValue()); })); } } 

hashmap为什么线程不安全

JDK1.7 中,由于多线程对HashMap进行扩容,调用了HashMap#transfer(),具体原因:某个线程执行过程中,被挂起,其他线程已经完成数据迁移,等CPU资源释放后被挂起的线程重新执行之前的逻辑,数据已经被改变,造成死循环、数据丢失。

本人自己实现的resize()方法:

 public void resize(){ // get every entry in the old table Set<Entry<K, V>> entrySet = myEntrySet(); // update length and threshold length*=2; threshold= (int) (length*LOAD_FACTOR); // 建个新表 // 把键值对项按hash规则挂到合适的地方 Entry<K,V>[] newTable = new Entry[length]; for (Entry<K, V> entry:entrySet){ entry.next=null; int index = indexFor(entry.key.hashCode()); if (newTable[index]==null){ newTable[index] = entry; }else { Entry<K,V> temp = newTable[index]; while (temp.next!=null){ temp=temp.next; } temp.next=entry; } } // 更新 table table = newTable; newTable = null; } 

hashmap hashtable concurrent hashmap 的关系

面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别 - 猿人谷 - D1h.Net第一号博客 (cnblogs.com)

联系:

都是 Map 接口的实现

都采用了 链表+数组 的实现方式

区别:

从线程安全角度

hashmap 线程不安全,没有锁机制

其他两个都是线程安全的

从键的角度

hashmap可以存储null键

其他两个都不可以

posted @ 2021-09-16 23:59  wqybokeyuan  阅读(4)  评论(0编辑  收藏  举报
Copyright © 2021 wqybokeyuan
Powered by .NET 6 on Kubernetes

问答 28u iTmz.Net 3q科技 A8团队1 A8团队2 A8团队3 A8备