MyHashMap
Map Interface
keySet 主要作用于HashSet
package _10_Hash;
import java.util.Iterator;
public interface IMap<K, V> {
/**
* 清除所有键值对
*/
void clear();
/**
* key是否已存在
*
* @param key
* @return
*/
boolean containsKey(K key);
/**
* value是否已存在
*
* @param value
* @return
*/
boolean containsValue(V value);
/**
* 根据key获得valye
*
* @param key
* @return
*/
V get(K key);
/**
* map 是否为空
*
* @return
*/
boolean isEmpty();
/**
* 所有 key组成的数组
* 和java api区分 所以用数组
*
* @return
*/
MyHashSet<K> keySet();
/**
* 存入键值对
*
* @param key
* @param value
* @return
*/
void put(K key, V value);
/**
* 把另外一个map中的所有键值对 存入到当前map中
*
* @param map
*/
void putAll(IMap<? extends K, ? extends V> map);
/**
* 根据key删除一个键值对
* @param key
* @return
*/
V remove(K key);
/**
* 键值对的个数
* @return
*/
int size();
/**
* 所有的value组成的数组
* @return
*/
V[] values();
/**
* 迭代器
* @return
*/
Iterator<MyHashMap.Node> iterator();
}
MyHashMap
这里用拉链法实现 put
迭代器的实现算法比较关键~~
package _10_Hash;
import java.util.Iterator;
public class MyHashMap<K,V> implements IMap<K,V> {
/**
* Node节点
*
* @param <K>
* @param <V>
*/
public static class Node<K, V> {
K key;
V value;
Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", value=" + value +
'}';
}
}
//创建桶
int N = 16;
private Node[] buckets = new Node[N];
private int size = 0;
@Override
public void clear() {
for (int i = 0; i < buckets.length; i++) {
buckets[i] = null;
}
size=0;
}
@Override
public boolean containsKey(K key) {
int index = hash1(key);
if (buckets[index] == null)//查看有没有对应的桶
return false;
else {
Node<K, V> p = buckets[index];//在链表中找key
while (p != null) {
K k1 = p.key;
//借用java机制 hashCode和 equals都来源与 Object 用户可以改写这两个方法制定对象相等的原则
//k1==key 比较的是对象的地址 java 默认 hashCode和equals都是基于对象地址
if (k1 == key || k1.hashCode() == key.hashCode() && k1.equals(key)) {
return true;
}
p = p.next;
}
}
return false;
}
@Override
public boolean containsValue(Object value) {
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
Node<K, V> p = buckets[i];
while (p != null) {
if (p.value.equals(value))
return true;
p = p.next;
}
}
}
return false;
}
@Override
public V get(K key) {
int index = hash1(key);//先看看有没有这个key的桶
if (buckets[index] == null) {
return null;
} else {
Node<K, V> p = buckets[index];
while (p != null) {
K k1 = p.key;
if (k1 == key || k1.equals(key) && k1.hashCode() == key.hashCode()) {
return p.value;
}
p = p.next;
}
}
return null;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public MyHashSet<K> keySet() {
MyHashSet<K> set = new MyHashSet<>();
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
Node<K, V> p = buckets[i];
while (p != null) {
set.add(p.key);
p = p.next;
}
}
}
return set;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
Node<K, V> p = buckets[i];
while (p != null) {
sb.append("(" + p.key + "," + p.value + ")" + ",");
p = p.next;
}
}
}
return sb.toString();
}
/**
* 解决冲突的时候使用拉链法
* 相同替换 不同就追加
* @param key
* @param value
*/
@Override
public void put(K key, V value) {
Node<K, V> node = new Node<>(key, value);
int index = hash1(key);//算出在桶中的位置
if (buckets[index] == null) {//桶子中没有东西 确定链表的表头
buckets[index] = node;
size++;
} else {
Node<K, V> p = buckets[index];//链表的表头找到
while (p != null) {//遍历链表 从头开始
K k1 = p.key;
if (key == k1 || key.hashCode() == k1.hashCode() && key.equals(k1)) {//存在key相同就覆盖
p.value = value;//存在相同的key 则更新value
break;
}
if (p.next == null) {//最后一个
p.next = node;
size++;
break;
}
p = p.next;// 没有 相同key 也不是最后一个 指针后移
}
}
}
/**
* 算出在桶中的位置
*
* @param key
* @return
*/
private int hash1(K key) {
return key.hashCode() % N;
}
@Override
public void putAll(IMap<? extends K, ? extends V> map) {
}
@Override
public V remove(K key) {
int index = hash1(key);
if (buckets[index] == null) {
return null;
} else {
//单向链表移除某个节点需要两个指针
Node<K, V> p = buckets[index];//表头
Node<K, V> pre = p;
while (p != null) {
K k1 = p.key;
if (k1 == key || k1.hashCode() == key.hashCode() && k1.equals(key)) {
//匹配到了移除
if (p == pre) {//是头结点
buckets[index] = pre.next;//buckets[index]相当于单链表的first
} else {
pre.next = p.next;//原本 pre.next==p
}
size--;
return p.value;
}
pre = p;
p = p.next;
}
}
return null;
}
@Override
public int size() {
return size;
}
@Override
public V[] values() {
return null;
}
//内部类迭代器
private class MapIterator implements Iterator<MyHashMap.Node> {
int i = 0;
Node p = buckets[0];
@Override
public boolean hasNext() {
while (p == null && i < N) {
i++;
if (i == N)
p = null;
else
p = buckets[i];
}
//i是一个非空的桶子 p是链表头
return p != null;
}
@Override
public Node next() {
Node res = p;
p = p.next;
return res;
}
}
@Override
public Iterator<MyHashMap.Node> iterator() {
return new MapIterator();
}
}
Test
package _10_Hash;
import org.junit.Before;
import org.junit.Test;
import java.util.Iterator;
public class MyHashSetTest {
MyHashSet<Integer> set = new MyHashSet<>();
@Before
public void add() {
set.add(1);
set.add(2);
set.add(3);
set.add(1);
}
@Test
public void remove() {
System.out.println(set);
set.remove(1);
System.out.println(set);
}
@Test
public void clear() {
set.clear();
System.out.println(set);
}
@Test
public void contains() {
System.out.println(set.contains(1));
System.out.println(set.contains(66));
}
@Test
public void isEmpty() {
System.out.println(set.isEmpty());
set.clear();
System.out.println(set.isEmpty());
}
@Test
public void size() {
System.out.println(set.size());
set.remove(1);
System.out.println(set.size());
System.out.println(set);
set.clear();
System.out.println(set.size());
System.out.println(set);
}
@Test
public void iter() throws Exception {
Iterator<Integer> iter = set.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
}
}HashFunctions
关于Hash的各种求法
提高key的分散程度~
简单版的优化空间
java HashMap 优化
本文作者：Author： 寒光博客
文章标题：[java] HashMap的简单实现
本文地址：https://dxoca.cn/java/312.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
本文地址：https://dxoca.cn/java/312.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
