最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

世界微资讯！手撕HashMap

来源：博客园


【资料图】

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 {    /**     * 将键值对存入我们自己实现的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@AllArgsConstructorpublic class Entry {    private K key;    private V value;}

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

import java.util.ArrayList;import java.util.LinkedList;import java.util.List;public class FakeHashMap implements FakeMap {    /**     * 定义一个数组，数组的下标和hashcode值对应，用来存放链表的地址     */    LinkedList>[] mapArr = new LinkedList[2000];    /**     * 不需要遍历数组，大大减少了代码量，直接存入hashcode的值     * 用来记录被使用的hashcode，方便后续其他方法的操作     */    List 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 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 entry : mapArr[hashcode]            ) {                if (entry.getKey().equals(key)) {                    entry.setValue(value);                    found = true;                    //若找到则退出循环                    break loop;                }            }            if (!found) {                mapArr[hashcode].add(new Entry(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 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保存     *     * @return 返回key的集合     */    Set keySet();    /**     * 得到 HashMap 中各个键值对映射关系的集合     *     * @return 返回一个映射关系的集合     */    Set> entrySet();    /**     * 将指定所有的键值对插入到 HashMap 中     *     * @param fakeMap 包含插入到 HashMap 的映射关系     */    void putAll(FakeMap fakeMap);    /**     * 得到 HashMap 键值对的数量     *     * @return 一个int型整数     */    int size();    /**     * 获取HashMap中value的集合     *     * @return 返回value集合     */    Collection values();

关键词：