欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

关于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;
        }

    }
}