如何实现一个简单的HashMap？

本文共计1158个文字，预计阅读时间需要5分钟。

javaimport java.util.*;

public class ThirdHashMap { // 链表节点 private static class Node { K key; V value; Node next;

Node(K key, V value, Node next) { this.key=key; this.value=value; this.next=next; } }

private Node[] table; private int capacity; private int size;

public ThirdHashMap() { this.capacity=16; this.table=new Node[capacity]; this.size=0; }

// 哈希函数 private int hashCode(K key) { return key==null ? 0 : key.hashCode(); }

// 获取节点 private Node getNode(K key) { int index=indexFor(key); Node node=table[index]; while (node !=null) { if (key.equals(node.key)) { return node; } node=node.next; } return null; }

// 获取索引 private int indexFor(K key) { int h=hashCode(key); return h % capacity; }

// 添加键值对 public void put(K key, V value) { Node node=getNode(key); if (node !=null) { node.value=value; return; }

int index=indexFor(key); Node newNode=new Node(key, value, table[index]); table[index]=newNode; size++;

// 扩容 if (size >=capacity * 0.75) { capacity *=2; Node[] oldTable=table; table=new Node[capacity]; size=0; for (Node node : oldTable) { while (node !=null) { put(node.key, node.value); node=node.next; } } } }}

import java.util.*; /** * @Author nanfengnan * @Date 2022/4/19 * @Description 自己实现的HashMap * 哈希函数:hashCode()+除留余数法 * 冲突解决:链地址法 */ public class ThirdHashMap<K, V> { /** * 链表节点 * @param <K> * @param <V> */ class Node<K,V>{ private K key; private V value; private Node<K,V> next; public Node(K key,V value){ this.key = key; this.value = value; this.next = null; } } // 默认容量 final int DEFAULT_CAPACITY = 16; // 负载因子 final float LOAD_FACTOR = 0.75f; // HashMap的大小 private int size; // 桶数组 Node<K,V>[] buckets; /** * 两个构造函数,用于初始化桶的大小 */ public ThirdHashMap() { buckets = new Node[this.DEFAULT_CAPACITY]; this.size = 0; } public ThirdHashMap(int capacity) { buckets = new Node[capacity]; this.size = 0; } /** * 哈希函数:采用除留余数法 * @param key * @param length * @return 哈希地址 */ public int getIndex(K key,int length) { // 获取hash code ,32位带符号数 int hashCode = key.hashCode(); // 除留余数法 return Math.abs(hashCode % length); } /** * 得到value方法 * @param key * @return */ public V get(K key) { // 获得key的哈希地址 int index = getIndex(key, buckets.length); Node<K, V> node = buckets[index]; // buckets[index]里面没有数据 if (node == null) return null; // 否则遍历链表 while (node != null) { // 考虑字符串使用equals if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) { return node.value; } node = node.next; } return null; } /** * put方法 * @param key * @param value */ public void put(K key,V value) { // 判断是否超过负载空间 if (size >= buckets.length*LOAD_FACTOR) resize(); putValue(key,value,buckets); } /** * 得到桶中元素个数 * @return */ public int size() { return this.size; } /** * 删除key * @param key */ public Node<K,V> remove(K key) { // 得到哈希地址 int index = getIndex(key, buckets.length); if (buckets[index] == null) return buckets[index]; else if ((buckets[index].key.hashCode() == key.hashCode()) && (buckets[index].key == key || buckets[index].key.equals(key))) { Node<K,V> t = buckets[index].next; buckets[index].next = t.next; return t; } Node<K,V> node = buckets[index].next; Node<K,V> pre = node; while (node != null) { // 找到了key,则断链删除元素 if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) { pre.next = node.next; return node; } pre = pre.next; node = node.next; } // 否则,桶中没有此元素 return null; } /** * containsKey * @param key * @return */ public boolean containsKey(K key) { for (int i = 0; i < buckets.length; i++) { if (buckets[i] == null) continue; Node node = buckets[i]; while (node != null) { if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) return true; node = node.next; } } return false; } /** * containsValue * @param value * @return */ public boolean containsValue(V value) { for (int i = 0; i < buckets.length; i++) { if (buckets[i] == null) continue; Node node = buckets[i]; while (node != null) { if ((node.value == value || node.value.equals(value))) return true; node = node.next; } } return false; } /** * 得到keySet * @return */ public Set<K> keySet() { Set<K> set = new HashSet<K>(); for (int i = 0; i < buckets.length; i++) { if (buckets[i] == null) continue; Node<K,V> node = buckets[i]; while (node != null) { set.add(node.key); node = node.next; } } return set; } /** * 得到values * @return */ public Collection<V> values() { Collection<V> collection = new ArrayList<V>(); for (int i = 0; i < buckets.length; i++) { if (buckets[i] == null) continue; Node<K,V> node = buckets[i]; while (node != null) { collection.add(node.value); node = node.next; } } return collection; } /** * 向桶中添加元素,也可以当作复制元素使用 * @param key * @param value * @param table */ public void putValue(K key,V value,Node<K,V>[] table) { // 获取哈希地址,判断是否存在 int index = getIndex(key, table.length); // 得到table[index]元素 Node<K,V> node = table[index]; // 桶中没有元素 if (node == null) { table[index] = new Node<K, V>(key,value); size++; return; } // 冲突,使用链地址法 while (node != null) { // key相同则修改,考虑字符串 if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) { node.value = value; } node = node.next; } // 没有该映射,添加到链表的头部 Node<K,V> t = new Node<K, V>(key,value); t.next = table[index].next; table[index].next = t; size++; } /** * 扩容函数 */ private void resize() { // 扩容2倍 Node<K,V>[] newbuckest = new Node[buckets.length<<1]; // 将当前元素写入newbuckets桶中 rehash(newbuckest); // buckets指向newbuckets buckets = newbuckest; } /** * 将酒桶的元素复制到新的桶中 * @param newbuckets */ private void rehash(Node<K,V>[] newbuckets) { size = 0; for (int i = 0; i < buckets.length; i++) { if (buckets[i] == null) continue; // 复制链表节点 Node<K,V> node = buckets[i]; while (node != null) { putValue(node.key,node.value,newbuckets); node = node.next; } } } }