手撕HashMap(二)

  • 这里再补充几个手撕HashMap的方法

1、remove()

  1. remove 方法参数值应该是键值对的键的值,当传入键值对的键的时候,remove 方法会删除对应的键值对
  2. 需要利用我们自己先前创建的 hashcodeList 来实现,hashcodeList 存入了所有被使用的 hashcode 值,方便后续的操作
  3. 在 put() 中,当添加新的键值对时,就会调用hashcodeList.add(hashcode);来存入添加的 hashcode 值
  4. hashcodeList:
    /**
     * 不需要遍历数组,大大减少了代码量,直接存入hashcode的值
     * 用来记录被使用的hashcode,方便后续其他方法的操作
     */
    List<Integer> hashcodeList = new ArrayList<>();
  1. remove() 方法的思路:
    • 根据传入的 key 的值,遍历 hashmap
    • 当 key 的值相同时,删除它,与此同时遍历 hashcodeList
    • 当 hashcodeList 中存储的哈希值与 key 通过 hashcode(key) 方法后得到的哈希值相等时,删除这个 hashcodeList 值
  2. 代码:
     /**
     * 删除传入的key值所对应的键值对对象
     *
     * @param key 传入的key
     */
    @Override
    public void remove(K key) {
        int hashcode = hashcode(key);
        for (Entry<K, V> entry : mapArr[hashcode]
        ) {
            //要把hashcodeList中的hashcode删除
            hashcodeList.removeIf(integer -> hashcode(entry.getKey()) == integer);
            //删除 mapArr 
            if (entry.getKey().equals(key)) {
                mapArr[hashcode].remove();
            }
        }
    }

2、clear()

  1. clear 方法调用之后,会清除 hashmap 中所有的关联或映射,即清除所有的 key、value
  2. 思路:
    • hashcodeList 中存储的是使用过的哈希值,而 mapArr 的下标是对应的哈希值,存储的是对应的value值
    • 遍历 hashcodeList,将里面的值一个个取出来并放到 mapArr 的下标,一一调用 remove 方法
    /**
     * 清除 HashMap 中的所有关联或者映射
     */
    @Override
    public void clear() {
        for (int i = 0; i < hashcodeList.size(); i++) {
            for (Entry<K, V> entry : mapArr[hashcodeList.get(i)]
            ) {
                mapArr[hashcodeList.get(i)].remove();
                //同时要把hashcodeList中的hashcode清除
                hashcodeList.clear();
            }
        }
    }

3、containsKey()

  1. 传入一个 key 的值,判断是否存在这个键所对应的键值对,存在则返回 true,不存在则返回 false
  2. 思路:
    • 先生成传入 key 的对应的哈希值
    • 判断下标为这个哈希值的数组是否为空,为空则直接返回 false
    • 如果不为空,则遍历这个数组找到相同的 key 则返回 true,否则返回 false
    • 会出现数组下标越界,如果出现,则说明不存在这个下标,自然也不存在这个哈希值,所以可以用 try、catch 环绕直接返回false
    /**
     * 判断是否存在key值所对应的映射,返回一个布尔值
     *
     * @param key 传入一个key的值
     * @return 判断是否存在key值所对应的映射,返回一个布尔值
     */
    @Override
    public boolean containsKey(K key) {
        int hashcode = hashcode(key);
        try {
            //如果发现没存过,直接返回false
            if (null == mapArr[hashcode]) {
                return false;
            } else {
                //如果遍历能查找到key,则返回true
                //如果遍历不能找到,则返回null
                for (Entry<K, V> entry : mapArr[hashcode]
                ) {
                    if (entry.getKey().equals(key)) {
                        return true;
                    }
                }
            }
        } catch (ArrayIndexOutOfBoundsException e) {
            //只要出现数组下标越界就说明没找到,直接返回false
            return false;
        }
        return false;
    }

4、keySet()

  1. 作用很简单,返回一个集合,集合包含了所有的 key 的值
  2. 注意:是 key 的值,而不是哈希值
  3. 思路:
    • 当 hashcodeList 为空时,说明没有哈希值,自然也不存在 key,所以直接返回 null
    • 否则遍历 mapArr 数组,下标为 hashcodeList 存储的哈希值,用 getKey 取出 key
    /**
     * 获取HashMap的键的集合,以Set<K>保存
     *
     * @return 返回key的集合
     */
    @Override
    public Set<K> keySet() {
        //若没有hashcode值,直接返回空
        if (null == hashcodeList) {
            return null;
        } else {
            Set<K> kSet = new HashSet<>();
            for (int i = 0; i < hashcodeList.size(); i++) {
                //遍历 mapArr
                for (Entry<K, V> entry : mapArr[hashcodeList.get(i)]
                ) {
                    kSet.add(entry.getKey());
                }
            }
            return kSet;
        }
    }

5、values()

  1. 与 keySet 类似,作用是返回一个集合,其中包含了所有的 value 值
  2. 思路:
    • 当 hashcodeList 为空时,说明没有哈希值,自然也不存在 key,自然也不存在 value,所以直接返回 null
    • 否则遍历 mapArr 数组,下标为 hashcodeList 存储的哈希值,用 getValue 取出 value
    /**
     * 获取HashMap中value的集合
     *
     * @return 返回value集合
     */
    @Override
    public Collection<V> values() {
        //如果没有hashcode值,则直接返回空
        if (null == hashcodeList) {
            return null;
        } else {
            //生成一个集合
            Collection<V> vCollection = new ArrayList<>();
            for (int i = 0; i < hashcodeList.size(); i++) {
                //遍历 mapArr
                for (Entry<K, V> entry : mapArr[hashcodeList.get(i)]
                ) {
                    vCollection.add(entry.getValue());
                }
            }
            return vCollection;
        }
    }

6、entrySet()

  1. 返回一个集合,包含了所有的键值对及其映射关系
  2. 思路:
    • 当 hashcodeList 为空时,说明没有哈希值,自然也不存在 key,自然也不存在 value,所以直接返回 null
    • 否则遍历 mapArr 数组,下标为 hashcodeList 存的哈希值,直接调用 add 方法添加
    /**
     * 得到 HashMap 中各个键值对映射关系的集合
     *
     * @return 返回一个映射关系的集合
     */
    @Override
    public Set<Entry<K, V>> entrySet() {
        //若没有hashcode值,直接返回空
        if (null == hashcodeList) {
            return null;
        } else {
            Set<Entry<K, V>> entrySet = new HashSet<>();
            for (int i = 0; i < hashcodeList.size(); i++) {
                //遍历 mapArr
                for (Entry<K, V> entry : mapArr[hashcodeList.get(i)]
                ) {
                    entrySet.add(entry);
                }
            }
            return entrySet;
        }
    }

7、size()

  1. size 方法就是返回一个 int 值,是 hashmap 的键值对的数量
  2. 思路:很简单,遍历 hashcodeList,存在一个哈希值就说明存在一对键值对,直接加一即可
    /**
     * 得到 HashMap 键值对的数量
     *
     * @return 一个int型整数
     */
    @Override
    public int size() {
        int count = 0;
        for (int i = 0; i < hashcodeList.size(); i++) {
            count++;
        }
        return count;
    }

原文链接:https://www.cnblogs.com/lynnier/p/17270880.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:手撕HashMap(二) - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • 滑动窗口总结

    前言 滑动窗口是双指针的一种特例,可以称为左右指针,在任意时刻,只有一个指针运动,而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。 好处:时间复杂度 O(n^2) —> O(n) 一、算法应用场景 关键词: 1.满足XXX条件(计算结果、出现次数、同时包含) 2.最长/最短/或最值 3.子串/子数组/子序列 最最最…

    算法与数据结构 2023年4月17日
    00
  • C语言数据结构之迷宫求解问题

    C语言数据结构之迷宫求解问题攻略 1. 前言 迷宫求解问题是计算机科学中一个经典的问题,也是许多初学者接触数据结构和算法时常用的题目。本文将通过C语言实现一个迷宫求解算法,介绍迷宫求解问题的基本思路和实现方法。 2. 迷宫求解问题的基本思路 迷宫求解问题的基本思路是利用深度优先搜索(DFS)或广度优先搜索(BFS)的算法去遍历整个迷宫,直到找到出口为止。在实…

    数据结构 2023年5月17日
    00
  • python实现ROA算子边缘检测算法

    下面是详细讲解“Python实现ROA算子边缘检测算法”的完整攻略,包括ROA算子的定义、ROA算子的实现、ROA算子的应用和两个示例说明。 ROA算子定义 ROA算子是一种基于局部方向性的边缘检测算法,它可以检测出图像中的边缘,并且可以保留边缘的方向信息。ROA算子的核心思想是在图像中寻找像素点的局部方向,并将其与周围像素点的方向进行比较,从而确定该像素点…

    python 2023年5月14日
    00
  • python八大排序算法速度实例对比

    Python八大排序算法速度实例对比 排序算法是计算机科学中的基本问题之一,它的目的是将一组数据按照定的顺序排列。在Python中,可以使用多种排序算法来对数据进行。本文将介绍Python的八大排序算法,并对它们的速度进行实例对比。 八大排序算法 1. 冒泡排序 冒泡排序是一种简单的排序算法,它的基本思想是通过断交换相邻的元素,将较大的元素逐渐“冒泡”到数组…

    python 2023年5月13日
    00
  • Java数据结构之循环队列简单定义与用法示例

    Java数据结构之循环队列简单定义与用法示例 什么是循环队列? 循环队列是一种数据结构,它具有先进先出(FIFO)的特点,即最先进队列的元素总是被最先取出。不同于普通队列,循环队列的尾指针指向数组的头部,因此可以实现循环利用数组空间,提高存储空间的利用率,避免因队列的操作大量移动数组元素而导致的时间浪费。 循环队列的基本操作 循环队列的基本操作包括:入队、出…

    数据结构 2023年5月17日
    00
  • 详解快速排序算法原理与使用方法

    快速排序算法是一种基于比较的排序算法,其使用递归的方法对待排序序列进行排序。快速排序的特点是可以通过递归的方式,在每次排序中选择一个元素作为枢轴(pivot),将待排序序列分成两个部分,其中一个部分所有元素都比枢轴小,另一个部分所有元素都比枢轴大,然后对这两个部分分别递归进行快速排序,直到所有元素都排序完成。 下面是快速排序算法的完整攻略: 快速排序的基本思…

    算法 2023年3月27日
    00
  • python K近邻算法的kd树实现

    以下是关于“Python K近邻算法的kd树实现”的完整攻略: 简介 K近邻算法是一种常用的分类算法,它通过计算样本之间的距离来确定最近的K个邻居,并使用它们的标签来预测新样本的标签。kd树是一种常用的数据结构,它可以加速K近邻算法的计算。本教程将介绍如何使用Python实现K近邻算法的kd树实现,并提供两个示例。 K近邻算法 K近邻算法是一种常用的分类算法…

    python 2023年5月14日
    00
  • python常见排序算法基础教程

    下面是关于“Python常见排序算法基础教程”的完整攻略。 1. 排序算法简介 排序算法是一种将一组数据按照一定规则进行排列的算法。在Python中,常见的算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。 2. Python实现常见排序算法 2.1 冒泡排序 冒泡排序是一种通过交换相邻元素来排序的算法。Python中,我们可以使用以下代码实现冒泡…

    python 2023年5月13日
    00
合作推广
合作推广
分享本页
返回顶部