手撕HashMap(二)

2023-07-31

这里再补充几个手撕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;
}

手撕HashMap(二)的相关教程结束。

《手撕HashMap(二).doc》

下载本文的Word格式文档,以方便收藏与打印。