手撕HashMap(一)
阅读原文时间:2023年08月25日阅读:5

HashMap基本了解


1、 jdk1.7之前,HashMap底层只是数组和链表

2、 jdk1.8之后,HashMap底层数据结构当链表长度超过8时,会转为红黑树

3、 HashMap利用空间换时间的思想,将键值对一个个散落在集合中

4、 hashcode值通过调用hashcode()方法得到,所以有可能存在hashcode值相同的情况,即所谓的哈希冲突

5、手撕hashmap的思路:

6、存储put():

  • Map有一个封装的内部接口Entry,用来将key和value封装成键值对对象
  • 键值对对象根据计算的hashcode值进行存储
  • hashmap的特点
    • key不能重复
    • 当key重复时,会把原有的键值对替换成新的键值对

7、取值get():

  • 先调用hashcode方法进行计算,判断是否存在

    • 存在则在链表中进行equals方法一一比较他们的key
    • key值不重复

手撕HashMap

1、首先需要一个Map接口,其中定义我们的put()、get()、hashcode()等方法

public interface FakeMap<K,V> {

    /**
     * 将键值对存入我们自己实现的FakeMap中
     * @param key    传入的key
     * @param value  key所对应的值
     */

    void put(K key,V value);

    /**
     * 通过传入key来获取对应的值
     * @param key 传入的key
     * @return    返回key对应的值,没有则返回null
     */
    V get(K key);

    /*
        说明:
        hashmap所使用的hashcode方法应该来自于key本身提供
        1、我们在模拟hashmap时,需要保证hashcode值的范围,不能超过数组的下表
        2、jdk1.8之后接口内可以写静态方法和default方法
        3、如果两个对象的hashcode相同,对象不一定相同;
            如果对象相同,hashcode一定相同
     */

    /**
     * 自己定义的hashcode方法
     * @param key 需要计算hashcode值的key
     * @return  int类型的hashcode值,人为地将值限制在了0-1999
     */
    default int hashcode(K key){
        return key.toString().hashCode()%2000;
    }

}

2、需要一个Entry类,用来用我们传入的键值对生成键值对对象

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

@Data
@NoArgsConstructor
@AllArgsConstructor
public class Entry<K, V> {
    private K key;
    private V value;
}

3、需要一个Map的实现类,用来实现Map中的各个方法

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class FakeHashMap<K, V> implements FakeMap<K, V> {

    /**
     * 定义一个数组,数组的下标和hashcode值对应,用来存放链表的地址
     */
    LinkedList<Entry<K, V>>[] mapArr = new LinkedList[2000];

    /**
     * 不需要遍历数组,大大减少了代码量,直接存入hashcode的值
     * 用来记录被使用的hashcode,方便后续其他方法的操作
     */
    List<Integer> hashcodeList=new ArrayList<>();

    /**
     * 将键值对存入我们自己实现的FakeMap中
     * @param key    传入的key
     * @param value  key所对应的值
     */
    @Override
    public void put(K key, V value) {
        //根据key计算出key对应的hashcode值
        int hashcode = hashcode(key);
        //hashcode值对应的是数组的下标,应该先判断下标对应的链表是否存在,不存在就先创建
        if (null == mapArr[hashcode]) {
            //创建一个链表,并且将我们的key和value封装成键值对对象Entry并存入链表
            Entry<K, V> entry = new Entry(key,value);
            //链表的内存地址存入数组对应的下标处
            mapArr[hashcode] = new LinkedList<>();
            mapArr[hashcode].add(entry);
            hashcodeList.add(hashcode);
        } else {
            //链表存在说明之前已经有键值对存入,需要我们进行判断
            //需要遍历这个链表:1、如果找到key相同的,则更新链表替换 2、如果没有找到,直接新建对象存入
            boolean found = false;
            loop:
            for (Entry<K, V> entry : mapArr[hashcode]
            ) {
                if (entry.getKey().equals(key)) {
                    entry.setValue(value);
                    found = true;
                    //若找到则退出循环
                    break loop;
                }
            }
            if (!found) {
                mapArr[hashcode].add(new Entry<K, V>(key, value));
            }
        }
    }

    /**
     * 通过传入key来获取对应的值
     * @param key 传入的key
     * @return    返回key对应的值,没有则返回null
     */
    @Override
    public V get(K key) {
        int hashcode = hashcode(key);
        //如果发现没存过,直接返回空
        if (null == mapArr[hashcode]) {
            return null;
        } else {
            //如果遍历能查找到key,则根据key取出对应的下标的值,返回value
            //如果遍历不能找到,则返回null
            for (Entry<K, V> entry : mapArr[hashcode]
            ) {
                if (entry.getKey().equals(key)) {
                    return entry.getValue();
                }
            }
        }
        return null;
    }

}

4、最后写一个测试类,测试我们自己手搓的hashmap

  • 传入三个键值对,其中前两个的key值相同,看看是否会自己更新value值

    public class Test {
    public static void main(String[] args) {
    FakeMap fm = new FakeHashMap<>();
    fm.put("ikun","zhangsan");
    fm.put("ikun","lisi");
    fm.put("boy","wangwu");
    System.out.println(fm.get("ikun"));
    System.out.println(fm.get("boy"));
    }
    }

5、测试结果:可以发现lisi替换掉了同样是ikun的zhangsan

6、补充:HashMap还有很多其他的方法,我这里没有全部手撕下来,但是可以根据put和get的思路来做

  • 具体实现的话就是在接口中定义新的方法,并且在实现类中实现再去测试就完事了

    /**
    * 删除传入的key值所对应的键值对对象
    *
    * @param key 传入的key
    */
    void remove(K key);

    /**
     * 清除 HashMap 中的所有关联或者映射
     */
    void clear();
    
    /**
     * 判断是否存在key值所对应的映射,返回一个布尔值
     *
     * @param key 传入一个key的值
     * @return 判断是否存在key值所对应的映射,返回一个布尔值
     */
    boolean containsKey(K key);
    
    /**
     * 获取HashMap的键的集合,以Set<K>保存
     *
     * @return 返回key的集合
     */
    Set<K> keySet();
    
    /**
     * 得到 HashMap 中各个键值对映射关系的集合
     *
     * @return 返回一个映射关系的集合
     */
    Set<Entry<K, V>> entrySet();
    
    /**
     * 将指定所有的键值对插入到 HashMap 中
     *
     * @param fakeMap 包含插入到 HashMap 的映射关系
     */
    void putAll(FakeMap<K, V> fakeMap);
    
    /**
     * 得到 HashMap 键值对的数量
     *
     * @return 一个int型整数
     */
    int size();
    
    /**
     * 获取HashMap中value的集合
     *
     * @return 返回value集合
     */
    Collection<V> values();