手写一个简单的HashMap

简介: 手写一个简单的HashMap

什么是HashMap?

探讨HashMap之前我们要理清楚一个概念:哈希表

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

然后是HashMap的概念

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了非同步和允许使用 null 之外,HashMap 类与 Hashtable大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间,可为基本操作(get 和 put)提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”(桶的数量)及其大小(键-值映射关系数)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

解决哈希冲突的常用方法

为什么会产生哈希冲突?

网络异常,图片无法展示
|


如何解决哈希冲突?

  • 开放定址法
    所谓的开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将记录存入
  • 再哈希法
    再哈希法又叫双哈希法,有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数
    计算地址,直到无冲突。虽然不易发生聚集,但是增加了计算时间。
  • 链地址法
    链地址法的基本思想是:每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向
  • 建立公共溢出区
    这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

手写HashMap

/**
 * @desc: HashMap的简单实现
 * @author: YanMingXin
 * @create: 2021/8/9-9:46
 **/
public class MyHashMap<K, V> {
    /**
     * 默认容量16
     */
    private final int DEFAULT_CAPACITY = 16;
    /**
     * 内部存储结构
     */
    private Node[] table = new Node[DEFAULT_CAPACITY];
    /**
     * 长度
     */
    private int size = 0;
    /**
     * keySet
     */
    private Set<K> keySet;
    /**
     * 获取大小
     *
     * @return
     */
    public int size() {
        return this.size;
    }
    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }
    /**
     * get方法
     *
     * @param key
     * @return
     */
    public Object get(Object key) {
        int hashValue = hash(key);
        int i = indexFor(hashValue, table.length);
        for (Node node = table[i]; node != null; node = node.next) {
            if (node.key.equals(key) && hashValue == node.hash) {
                return node.value;
            }
        }
        return null;
    }
    /**
     * put方法
     *
     * @param key
     * @param value
     * @return
     */
    public Object put(Object key, Object value) {
        //通过key,求hash值
        int hashValue = hash(key);
        //通过hash,找到这个key应该放的位置
        int i = indexFor(hashValue, table.length);
        //i位置已经有数据了,往链表添加元素
        for (Node node = table[i]; node != null; node = node.next) {
            Object k;
            //且数组中有这个key,覆盖其value
            if (node.hash == hashValue && ((k = node.key) == key || key.equals(k))) {
                Object oldValue = node.value;
                node.value = value;
                //返回oldValue
                return oldValue;
            }
        }
        //如果i位置没有数据,或i位置有数据,但key是新的key,新增节点
        addEntry(key, value, hashValue, i);
        return null;
    }
    /**
     * 增加节点
     *
     * @param key
     * @param value
     * @param hashValue
     * @param i
     */
    public void addEntry(Object key, Object value, int hashValue, int i) {
        //如果超过了原数组大小,则扩大数组
        if (++size == table.length) {
            Node[] newTable = new Node[table.length * 2];
            System.arraycopy(table, 0, newTable, 0, table.length);
            table = newTable;
        }
        //的到i位置的数据
        Node eNode = table[i];
        //新增节点,将该节点的next指向前一个节点
        table[i] = new Node(hashValue, key, value, eNode);
    }
    /**
     * 获取插入的位置
     *
     * @param hashValue
     * @param length
     * @return
     */
    public int indexFor(int hashValue, int length) {
        return hashValue % length;
    }
    /**
     * 获取hash值
     *
     * @param key
     * @return
     */
    public int hash(Object key) {
        return key.hashCode();
    }
    /**
     * toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        ArrayList list = new ArrayList<Node>();
        for (Node node : table) {
            if (node != null) {
                list.add(node);
            }
        }
        return list.toString();
    }
    /**
     * 静态内部类
     */
    static class Node<V> {
        int hash;//hash值
        Object key;//key
        Object value;//value
        Node<V> next;//指向下个节点(单例表)
        Node(int hash, Object key, Object value, Node<V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public Object getKey() {
            return this.key;
        }
        public Object getValue() {
            return this.value;
        }
        @Override
        public String toString() {
            return "{" + key + ", " + value + "}";
        }
    }
}
复制代码


在本次HashMap的实现中就使用到了链地址法解决hash冲突,图示:

网络异常,图片无法展示
|


参考:

https://blog.csdn.net/m0_37499059/article/details/80623438

https://www.cnblogs.com/lyfstorm/p/11044468.html


相关文章
|
6月前
|
Serverless
手写一个简单的HashMap
手写一个简单的HashMap
40 0
|
索引
源码分析系列教程(11) - 手写Map框架(基于LinkedList)
源码分析系列教程(11) - 手写Map框架(基于LinkedList)
32 0
|
2月前
|
存储 Java 索引
手写一个简单版的ArrayList
手写一个简单版的ArrayList
|
6月前
|
索引
06 # 手写 map 方法
06 # 手写 map 方法
50 0
|
存储 算法 Java
java集合框架Map之HashMap底层原理解析
阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) , 当HashMap中的table数组(桶)的长度 >= 阈值的时候就会自动触发扩容机制
66 0
|
存储 Java 开发者
|
存储 算法 Java
【Java集合框架 二】HashMap源码分析
【Java集合框架 二】HashMap源码分析
87 0
|
网络协议 Java 数据库连接
HashMap源码手写简易篇(数组+链表)
HashMap源码手写简易篇(数组+链表)
|
存储 算法 安全
java集合之HashMap
HashMap作为面试必备题目,是需要每个java程序员都得研究的,这里总结下JDK8之后HashMap的实现。
166 0
java集合之HashMap
|
存储 Java Serverless
Java集合 - HashMap
本篇文章介绍 Java 集合中的 HashMap。 1、HashMap 的底层存储结构 2、HashMap 的新增操作的处理逻辑 3、HashMap 的数组扩容机制 4、HashMap 的查询操作的处理逻辑
109 0
Java集合 - HashMap