hashmap简单实现

p.p1 { margin: 0; font: 11px Monaco }
p.p2 { margin: 0; font: 11px Monaco; min-height: 15px }
p.p3 { margin: 0; font: 11px Monaco; color: rgba(79, 118, 203, 1) }
p.p4 { margin: 0; font: 11px Monaco; color: rgba(147, 26, 104, 1) }
p.p5 { margin: 0; font: 11px Monaco; color: rgba(119, 119, 119, 1) }
p.p6 { margin: 0; font: 11px Monaco; color: rgba(126, 80, 79, 1) }
p.p7 { margin: 0; font: 11px Monaco; color: rgba(78, 144, 114, 1) }
span.s1 { color: rgba(147, 26, 104, 1) }
span.s2 { color: rgba(145, 175, 203, 1) }
span.s3 { text-decoration: underline; color: rgba(145, 175, 203, 1) }
span.s4 { text-decoration: underline }
span.s5 { color: rgba(0, 0, 0, 1) }
span.s6 { color: rgba(3, 38, 204, 1) }
span.s7 { color: rgba(126, 80, 79, 1) }
span.s8 { color: rgba(78, 144, 114, 1) }
span.Apple-tab-span { white-space: pre }

import java.util.AbstractMap;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.ListIterator;

import java.util.Map;

import java.util.Set;

/**

记得很早之前看到过一篇帖子说一个面试者去面试某大厂要他当场写一个hashmap，其实今天讲的这个例子，足以应付那场面试，核心思想一应俱全，有些地方还欠完善。。。

这个simpleHashmap原理是如下实现

put:

首先定义一个基于链表的Entry hash桶数组

通过key的hashcode取模数组大小得到对应的hash桶下标

如果链表中没有找到对应的key 则加入当前hash桶中

否则覆盖Entry对象

get:

1.通过key的hashcode取模数组大小得到对应的hash桶

判断hash桶中是否存在Entry对象有取出；没有返回null.

<br>

以下是实际hashmap实现思路:

以Entry[]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。

插入元素时，如果两条Key落在同一个桶（比如哈希值1和17取模16后都属于第一个哈希桶），我们称之为哈希冲突。

JDK的做法是链表法，Entry用一个next属性实现多个Entry以单向链表存放。查找哈希值为17的key时，先定位到哈希桶，然后链表遍历桶里所有元素，逐个比较其Hash值然后key值。

在JDK8里，新增默认为8的阈值，当一个桶里的Entry超过閥值，就不以单向链表而以红黑树来存放以加快Key的查找速度。

当然，最好还是桶里只有一个元素，不用去比较。所以默认当Entry数量达到桶数量的75%时，哈希冲突已比较严重，就会成倍扩容桶数组，并重新分配所有原来的Entry。扩容成本不低，所以也最好有个预估值。

取模用与操作（hash & （arrayLength-1））会比较快，所以数组的大小永远是2的N次方，你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。

iterator（）时顺着哈希桶数组来遍历，看起来是个乱序

public class SimpleHashMap<K, V> extends AbstractMap<K, V> {

static final int SIZE = 997;

LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];

@Override

public V put(K key, V value) {

V oldValue = null;

int index = Math.abs(key.hashCode()) % SIZE;// 取模

if (buckets[index] == null) {

buckets[index] = new LinkedList<MapEntry<K, V>>();

}

LinkedList<MapEntry<K, V>> bucket = buckets[index];// 桶位【槽位】

MapEntry<K, V> pair = new MapEntry<K, V>(key, value);

boolean found = false;

ListIterator<MapEntry<K, V>> it = bucket.listIterator();

while (it.hasNext()) {

MapEntry<K, V> iPair = it.next();

if (iPair.getKey().equals(key)) {

oldValue = iPair.getValue();

it.set(pair);

found = true;

break;

}

if (!found) {

bucket.add(pair);

}

return oldValue;

}

@Override

public V get(Object key) {

int index = Math.abs(key.hashCode()) % SIZE;

if (buckets[index] == null) {

return null;

}

for (MapEntry<K, V> iPair : buckets[index]) {

if (iPair.getKey().equals(key)) {

return iPair.getValue();

}

return null;

}

@Override

public Set<Map.Entry<K, V>> entrySet() {

Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();

for (LinkedList<MapEntry<K, V>> bucket : buckets) {

if (bucket == null) {

continue;

}

for (MapEntry<K, V> mpair : bucket) {

set.add(mpair);

}

return set;

}

public static void main(String[] args) {

// SimpleHashMap<String, String> simpleHashMap=new SimpleHashMap<String,String>();

// simpleHashMap.putAll(Countries.capitals(25));

// System.out.println(simpleHashMap);

// System.out.println(simpleHashMap.get("ERITREA"));

// System.out.println(simpleHashMap.entrySet());

System.out.println(1 ^ 1); // 两个二进制比较相同取0 不同为一

}

巴特西

hashmap简单实现

最新文章

热门文章