HashMap基本了解
1、 jdk1.7之前，HashMap底层只是数组和链表
2、 jdk1.8之后，HashMap底层数据结构当链表长度超过8时，会转为红黑树
3、 HashMap利用空间换时间的思想，将键值对一个个散落在集合中
4、 hashcode值通过调用hashcode()方法得到，所以有可能存在hashcode值相同的情况，即所谓的哈希冲突
5、手撕hashmap的思路：
6、存储put()：
- Map有一个封装的内部接口Entry<K,V>，用来将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<String, String> 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();