数据结构之hash表，HashMap简单实现

左手的ㄟ右手 2022-08-06 06:05 114阅读 0赞

### Hash表概念 ###

在查找表中我们已经说过，在Hash表中，记录在表中的位置和其关键字之间存在着一种确定的关系。这样我们就能预先知道所查关键字在表中的位置，

从而直接通过下标找到记录。使查找时间复杂度接近O(1)。

1)哈希(Hash)函数是一个映象，即： 将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；

2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1¹ key2，而  f(key1)=f(key2)，这时候下标就出现冲突了。

3).只能尽量减少冲突而不能完全避免冲突，这是因为通常关键字集合比较大，其元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值在构造

这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。

### Hash构造函数的方法，及适用范围 ###

（1）直接定址法：

哈希函数为关键字的线性函数，H(key) = key 或者 H(key) = a\*key + b

此法仅适合于：地址集合的大小 ==关键字集合的大小，其中a和b为常数。

（2）数字分析法：

假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。

此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

（3）平方取中法：

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同 时平方值的中间各位又能受到整个关键字中各位的影响。

此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。

（4）折叠法：

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：移位叠加:将分割后的几部分低位对齐相加；间界叠加:从一端沿分割界来回折叠，然后对齐相加。

此法适于：关键字的数字位数特别多。

（5）除留余数法：

设定哈希函数为:H(key) = key%p( p≤m )，其中， m为表长，p 为不大于m的素数，或是不含20以下的质因子

（6）随机数法：

设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数

此法适于：对长度不等的关键字构造哈希函数。

实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表    长度（哈希地址范围），总的原则是使产生冲突的可能性降到尽可能地小。

### 三.Hash处理冲突方法，各自特征“处理冲突”的实际含义是：为产生冲突的关键字寻找下一个哈希地址。 ###

（1）开放定址法：

为产生冲突的关键字地址 H(key)求得一个地址序列： H0, H1, H2, …, Hs 1≤s≤m-1，Hi =( H(key)+di)%m，其中： i=1, 2, …,s，H(key)为哈希函数;m为哈希表长;

（2）链地址法：

将所有哈希地址相同的记录都链接在同一链表中。

![Center][]

（3）再哈希法：

方法：构造若干个哈希函数，当发生冲突时，根据另一个哈希函数计算下一个哈希地址，直到冲突不再发 生。即：Hi=Rhi(key)i=1,2,……k，其中：Rhi——不同的哈希函数，特点：计算时间增加

四.Hash查找过程

对于给定值 K,计算哈希地址 i = H(K)，若 r\[i\] = NULL则查找不成功，若 r\[i\].key = K则查找成功、

否则 “求下一地址 Hi”，直至r\[Hi\] = NULL(查找不成功)或r\[Hi\].key = K(查找成功) 为止。

### 四、HashMap简单实现 ###

package com.sourcecode.hashmap;
    public class MyMap<K, V> {
            //测试
            public static void main(String[] args) {
                    MyMap map=new MyMap();
                    map.put("name", "admin");
                    map.put("age", 1);
                   
                    System.out.println(map.get("name"));
                    System.out.println(map.size);
            }
           
            private int size;//当前容量
            private static int INIT_CAPACITY=16;//默认容量
            private Entry<K,V> [] container;//实际存储数据的数组对象 
            private static float LOAD_FACTOR=0.75f;//装载因子 
            private int max;//能存的最大的数=capacity*factor
           
            public MyMap(int init_capacity,float load_factor){//构造函数
                    if(init_capacity<0){
                            throw new IllegalArgumentException("Illegal initial capacity:"+init_capacity);
                    }
                    if(load_factor<=0 || Float.isNaN(load_factor)){//格式是否合法
                            throw new IllegalArgumentException("Illegal load factor:"+load_factor);
                    }
                    this.LOAD_FACTOR=load_factor;
                    max=(int)(init_capacity*load_factor);
                    container=new Entry[init_capacity];
            }
        public MyMap() {//无参构造函数
          this(INIT_CAPACITY, LOAD_FACTOR);
        }
        //放入一个元素
        public boolean put(K k,V v){
             // 1.计算K的hash值 
             int hash=k.hashCode();//调用JDK给出的hashCode()方法来计算hash值
             //2、将所有信息封装为一个Entry 
             Entry<K,V> temp=new Entry(k,v,hash);
             if(setEntry(temp, container)){
                     //size加一
                     size++;
                     return true;
             }
             return false;
        }
        //得到一个元素
        public V get(K k){
             Entry<K,V> entry=null;
             int hash=k.hashCode();
             int index=indexFor(hash, container.length);
             entry=container[index];
             if(null== entry){
                     return null;
             }
             while(null!=entry){
                     if(k == entry.key || entry.key.equals(k)){
                             return entry.value;
                     }
             }
             return null;
        }
        /*为table中放入一个entry*/
        private boolean setEntry(Entry<K,V> temp,Entry [] table){
           int index=indexFor(temp.hash,table.length);//根据hash码产生数组下标
           Entry<K,V> entry=table[index];//先获取这个元素
           if(null!=entry){
                while(null!=entry){
                        if((temp.key == entry.key || temp.key.equals(entry.key ))&&temp.hash == entry.hash &&(temp.value == entry.value)||temp.value.equals(entry.value)){
                                  return false;
                        }elseif(temp.key!=entry.key&&temp.value!=entry.value){
                                if(null!=entry.next){
                                        break;
                                }
                                       entry=entry.next;
                        }
                }
                addEntry2Last(entry,temp);
           }else{
                setFirEntry(temp,index,table);//如果原table种这个位置为空
           }
           return true;
        }
        /*为table的这个索引设置第一个值*/
            private void setFirEntry(Entry<K, V> temp, int index, Entry[] table) {
                    if(size>max){
                            resize(table.length*4);
                    }
                    // 2.不超标，或者扩容以后，设置元素 
                    table[index]=temp;
                    //因为每次设置后都是新的链表，需要将其后接的结点都去掉
                    temp.next=null;
            }
            /*将entry加入到相应的位置*/
            private void addEntry2Last(Entry<K, V> entry, Entry<K, V> temp) {
             if(size>max){
              resize(container.length*4);
             }
             entry.next=temp;
            }
            /*重新设置表的大小*/
            private void resize(int newSize) {
             Entry<K,V> [] newTable=new Entry[newSize];
             max=(int)(newSize*LOAD_FACTOR);
             for(int j=0;j<container.length;j++){
              Entry<K,V> entry=container[j];
              //因为每个数组元素其实为链表，所以…………
              while(null!=entry){
                      setEntry(entry,newTable);
                      entry=entry.next;
              }
             }
             container=newTable;
            }
            /*得到数组下标*/
            private int indexFor(int hash, int length) {
                    return hash&(container.length-1);
            }
    }
    /*链表元素*/
    class Entry<K,V>{
            Entry<K, V> next;
            V value;
            K key;
            int hash;//这个key对应的hash码，作为一个成员变量，当下次需要用的时候可以不用重新计算
            public Entry(K k,V v, int hash) {
                    this.key=k;
                    this.value=v;
                    this.hash=hash;// 下一个结点 
            }
            public V getValue() {
                    return value;
            }
            public void setValue(V value) {
                    this.value = value;
            }
            public K getKey() {
                    return key;
            }
            public void setKey(K key) {
                    this.key = key;
            }
            public int getHash() {
                    return hash;
            }
            public void setHash(int hash) {
                    this.hash = hash;
            }
    }

[Center]: /images/20220806/da83b9074e854fc781d03d2421436e3c.png