目录
1.定义MyMap接口(可以理解为HashMap实现的Map接口）
1.定义MyMap接口(可以理解为HashMap实现的Map接口）
public interface MyMap<K, V> {
/**
* 定义put方法
*
* @param k
* @param v
* @return
*/
V put(K k, V v);
/**
* 定义get 方法
*
* @param k
* @return
*/
V get(K k);
/**
* 定义长度
*
* @return
*/
int size();
/**
* 删除一个元素
* @param k
* @return
*/
boolean remove(K k);
/**
* 定义规范
*
* @param <K>
* @param <V>
*/
interface Entry<K, V> {
K getKey();
V getValue();
}
}2 实现接口及参数解释
public class MyHashMap<K, V> implements MyMap<K, V> {
//容器
private Entry<K, V>[] table = null;
private int mapLength = 16;
//计算临界值负载因子
private static final double CRITICAL_VALUE = 0.75;
//临界值 扩容用的
private int threshold = (int) Math.ceil(mapLength * CRITICAL_VALUE);
private int size = 0;
public MyHashMap() {
table = new Entry[mapLength];
}
public MyHashMap(int mapLength) {
this.mapLength = mapLength;
}
class Entry<K, V> implements MyMap.Entry<K, V> {
K key;
V value;
int index;
Entry<K, V> next;
public Entry(K key, V value, int index, Entry<K, V> next) {
this.key = key;
this.value = value;
this.index = index;
this.next = next;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
}
@Override
public V put(K k, V v) {
return null;
}
@Override
public V get(K k) {
return null;
}
//简单，直接完成
@Override
public int size() {
return this.size;
}
@Override
public boolean remove(K k) {
return false;
}
}值得注意的就是前面的几个参数和一个内部类Entry：此类主要的参数有四个key，value，index，next，分别来做解释
key 和 value 对应 HashMap中put方法传进来的key 和value；
index对应的它在数组中的下表；next：当hash冲突的时候，就是指向下一个结点的元素；
其实可以简单理解为HashMap具体存的只是Entry，这个元素里存的具体参数，因为传进来的反省不能保证有next，而我们又需要next。
3，自定义HashCode
private int hashCode(Object key) {
if (key == null) {
return 0;
}
int h = key.hashCode();
return (h ^ (h >>> 16)) % this.mapLength;
}哈希算法如果不懂的可以百度一下，百度更加清晰些，简单解释就是通过hashcode计算他在数组中的具体下标。
4，重写put方法
public V put(K k, V v) {
//这里是扩容逻辑，可以看完扩容再来看下面的if
Entry<K, V>[] tab;
if ((tab = resize()) != null) {
this.table = tab;
}
//通过hashCode方法计算他的下标
int index = hashCode(k);
//通过下标拿元素
Entry<K, V> kvEntry = table[index];
//如果当前元素为空 直接把传进来的key和value放在当前位置，因为他没有next元素
//所以传null即可，然后数组长度+1；
if (kvEntry == null) {
table[index] = new Entry<>(k, v, index, null);
size++;
} else {//如果当前位置有元素：这里的主要的逻辑有两个，判重和添加
//保存旧的值
V oldValue;
//如果当前元素有下一个就继续便利
while (kvEntry.next != null) {
//如果当前key已经存在了，返回旧的值，对原来的值进行替换
if (kvEntry.getKey().equals(k)) {
oldValue = kvEntry.getValue();
kvEntry.value = v;
return oldValue;
} else {//否则继续查找下一个
kvEntry = kvEntry.next;
}
}
//便利到最后一个元素了，还没找到重复值，直接添加到链表尾
kvEntry.next = new Entry<>(k, v, index, null);
}
//返回value
return table[index].getValue();
}5，重写get方法
public V get(K k) {
int index = hashCode(k);
//通过哈希获取的index传入到下面的方法中
Entry<K, V> kvEntry = table[index];
return findValueByKey(k, kvEntry);
}
private V findValueByKey(K k, Entry<K, V> kvEntry) {
//如果当前下标的元素就是我们需要的值直接返回value
if (kvEntry != null && (k == kvEntry.getKey() || kvEntry.getKey().equals(k))) {
return kvEntry.getValue();
} else {//遍历链表，找到返回value
while (kvEntry != null) {
if (k == kvEntry.getKey() || kvEntry.getKey().equals(k)) {
return kvEntry.getValue();
}
kvEntry = kvEntry.next;
}
}
//找不到直接返回null
return null;
}6，重写remove方法
public boolean remove(K k) {
//老规矩，还是计算下标
int hashCode = hashCode(k);
//下标没有元素，说明这个key没插入过，返回false
if (table[hashCode] == null) {
return false;
}
//如果下标就是要删除的元素，让当前链表等于链表的下一个
else if (table[hashCode].getKey() == k || table[hashCode].getKey().equals(k)) {
table[hashCode] = table[hashCode].next;
size--;
return true;
} else {
//遍历链表删除元素，如果不懂可以做做链表的力扣,如果对链表中的元素进行删除，我没有
//就算size
Entry temp = table[hashCode];
while (temp.next != null) {
if (temp.next.getKey() == k || temp.next.getKey().equals(k)) {
temp.next = temp.next.next;
return true;
} else {
temp = temp.next;
}
}
}
//把所有情况做完了，说明这个key没插入过，返回false
return false;
}7，扩容方法
private Entry<K, V>[] resize() {
Entry<K, V>[] kvEntry = null;
//如果当前的容器为空，返回一个新的链表
if (this.table == null) {
Entry<K, V>[] entries = new Entry[mapLength];
return entries;
//如果当前容器不为空，需要创建新的容器，并把旧容器的每一个元素重新计算索引后放入到新的
//容器中，如果不这样做，会出现get不到的情况，因为我们的索引值也是和容器的长度有关的
// else if 里面的意思是如果当前容器长度大于了临界值，我们进行扩容
} else if (size >= (this.threshold)) {
//容器长度扩充2倍，临界值也扩充两倍
this.mapLength = this.mapLength * 2;
this.threshold *= 2;
kvEntry = new Entry[this.mapLength];
int hashCode;
//遍历添加
for (Entry entry : table) {
if (entry == null) {
continue;
}
//如果当前元素是链表，计算每一个元素的哈希值
if (entry.next != null) {
while (entry != null) {
kvEntry[hashCode(entry)] = entry;
entry = entry.next;
}
}
//直接添加
else {
hashCode = hashCode(entry.getKey());
kvEntry[hashCode] = entry;
}
}
}
//返回新节点，然后可以去看看put方法的第一个if
return kvEntry;
}具体代码都在gitee上，可以直接下载，写的不好，写的不对的地方还请指正。
版权声明：本文为weixin_57929476原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。