手撕HashMap（二）

2023-03-29 23:02 由琳妮尔发表于 #其他

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

1、remove()

remove 方法参数值应该是键值对的键的值，当传入键值对的键的时候，remove 方法会删除对应的键值对
需要利用我们自己先前创建的 hashcodeList 来实现，hashcodeList 存入了所有被使用的 hashcode 值，方便后续的操作
在 put() 中，当添加新的键值对时，就会调用hashcodeList.add(hashcode);来存入添加的 hashcode 值
hashcodeList：

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

remove() 方法的思路：
- 根据传入的 key 的值，遍历 hashmap
- 当 key 的值相同时，删除它，与此同时遍历 hashcodeList
- 当 hashcodeList 中存储的哈希值与 key 通过 hashcode(key) 方法后得到的哈希值相等时，删除这个 hashcodeList 值
代码：

     /**
     * 删除传入的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()

clear 方法调用之后，会清除 hashmap 中所有的关联或映射，即清除所有的 key、value
思路：
- 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()

传入一个 key 的值，判断是否存在这个键所对应的键值对，存在则返回 true，不存在则返回 false
思路：
- 先生成传入 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()

作用很简单，返回一个集合，集合包含了所有的 key 的值
注意：是 key 的值，而不是哈希值
思路：
- 当 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()

与 keySet 类似，作用是返回一个集合，其中包含了所有的 value 值
思路：
- 当 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()

返回一个集合，包含了所有的键值对及其映射关系
思路：
- 当 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()

size 方法就是返回一个 int 值，是 hashmap 的键值对的数量
思路：很简单，遍历 hashcodeList，存在一个哈希值就说明存在一对键值对，直接加一即可

    /**
     * 得到 HashMap 键值对的数量
     *
     * @return 一个int型整数
     */
    @Override
    public int size() {
        int count = 0;
        for (int i = 0; i < hashcodeList.size(); i++) {
            count++;
        }
        return count;
    }