关于HashMap那些事
程序员文章站
2022-05-04 18:57:01
...
1 什么是hash
它是将一个任意长度的二进制值(key)通过一个映射关系转换成一个固定长度的二进制值(value)
关键字:任意长度 映射关系(hash算法) 固定长度
固定长度的二进制值相当于一个任意长度的二进制值的一个摘要
2 hash表
特点:存储效率高,取数据的时间复杂度为1 o(1)
hash 通过一个key,通过一个哈希函数,找到数组中与这个key唯一映射的value
根据这个hash函数找到数组中这个value的下标
3 hash函数
key 找下标
除留取余数法(取模)
定义数 a的长度为16
int index=key%m;
m要取比数组长度小的最大质数,因此m为15
在hashmap存储时,若 key=1,value=23; int 1=1%15 因此value23这个值会被放在数组的第二个位置上
4 hash冲突
key=1和key=15取得的索引值都是1,这时便发生了hash冲突
解决方法
- 线性探测法 :探测的步长为1
- 链表形式 (jdk中hashmap中使用的)
实现一个HashMap
public interface DMap<K,V> {
V put(K key,V value);
V get(K key);
int size();
interface Entry<K,V>{
K getKey();
V getValue();
}
}
public class DHashMap<K,V> implements DMap<K, V> {
//数组长度 2的倍数
private static Integer defaultLength=16;
//负载因子
private static double defaultLoad=0.75;
private Entry<K,V>[] table=null;
//记录数组的元素个数
private int size=0;
DHashMap(double defaultLoad,int defaultLength){
this.defaultLength=defaultLength;
this.defaultLoad=defaultLoad;
table=new Entry[defaultLength];
}
DHashMap(){
this(defaultLoad,defaultLength);
}
@Override
public V put(K key, V value) {
int index=this.getIndex(key);
DHashMap<K, V>.Entry<K, V> entry = table[index];
if(entry==null){
//进行put操作
table[index]=new Entry(key,value,null,index);
size++;
}else{
//当前位置已经有元素了
Entry newEntry =new Entry(key,value,entry,index);
table[index]=newEntry;
}
return table[index].getValue();
}
@SuppressWarnings("null")
//返回存储数据的下标
public int getIndex(K key){
//取模
int m=this.defaultLength-1;
return key.hashCode() % m;
}
@Override
public V get(K key) {
int index=this.getIndex(key);
return table[index] == null?null:table[index].getValue();
}
@Override
public int size() {
return size;
}
class Entry<K,V> implements DMap.Entry<K, V>{
K key;
V value;
Entry<K,V> next;
//Entry在数组中的下标
int index;
Entry(K k,V v, Entry<K,V> n,int index){
key=k;
value=v;
next=n;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
}
}