关于java:持续输出面试题之算法散列技术

开篇介绍

大家好，我是 Java 最全面试题库 的提裤姐，明天这篇是数据结构与算法的第九篇，次要介绍散列技术；在后续，会沿着第一篇开篇的常识线路始终总结上来，做到日更！如果我能做到百日百更，心愿你也能够跟着百日百刷，一百天养成一个好习惯。

散列表

散列法又称哈希法，它在元素的存储地位与元素关键码间建设一个确定的对应函数关系Hash（），使每个关键码与构造中的一个惟一的存储地位绝对应：Address=Hash（Rec.key） 插入时，依照此函数计算存储地位并寄存，查找时对元素的关键码进行相应的函数计算，把求得的函数值与关键码进行比对，统一则查找胜利。依照此办法结构的表构造即为散列表

散列函数的构造方法

1. 间接定址法
能够间接应用f(key)=a*key+b，这样的模式获取 value 值

2. 平方取中法
先通过关键字的平方值扩充相近值的差异，而后依据表长度取两头几位数作为散列函数值。

int Hash(int key) {
  key *= key;
  key /= 100;
  return key%100;
}

3. 除留余数法
能够应用 f(key) = key % p 的办法去计算 value 值。

4. 随机数法
抉择一个随机函数，取关键字的随机函数值为他的散列地址，即 h(key) = random(key)

抵触解决办法

1. 凋谢定制法
所谓的凋谢定址法就是一旦产生了抵触，就去寻找下一个空的散列地址，只有散列表足够大，空的散列地址总能找到，并将记录存入。
公式：hi=(h(key) + di) % m
比如说，关键字汇合为 {12, 38, 26}，表长为 12。散列函数f(key) = key mod 12。
计算 key 等于 26 的时候求余是 2。然而 2 的地位曾经有值了，那么进行接下来的操作f(36) = (f(36)+1)mod 12，这个时候就没有值了。那么就有空位了。

这个就是线性探测法。

2. 拉链法
拉链法的解决办法是，当呈现抵触的时候，会把抵触值变成一个链表加在最初面。

拉链法也有毛病，就是链表数量一旦变得很大的时候，查找的性能变得很大。jdk 的解决办法是当链表长度大于 8 的时候变成红黑树。

散列表实现

public class HashTable<K, V> {  
    private int size;// 元素个数  
    private static int initialCapacity=16;//HashTable 的初始容量  
    private Entry<K,V> table[];// 理论存储数据的数组对象  
    private static float loadFactor=0.75f;// 加载因子  
    private int threshold;// 阀值，能存的最大的数 max=initialCapacity*loadFactor  
      
    // 结构指定容量和加载因子的结构器  
    public HashTable(int initialCapacity,float loadFactor){if(initialCapacity<0)  
            throw new IllegalArgumentException("Illegal Capacity:"+initialCapacity);  
        if(loadFactor<=0)  
            throw new IllegalArgumentException("Illegal loadFactor:"+loadFactor);  
        this.loadFactor=loadFactor;  
        threshold=(int)(initialCapacity*loadFactor);  
        table=new Entry[threshold];  
    }  
      
    // 应用默认参数的结构器  
    public HashTable(){this(initialCapacity,loadFactor);  
    }  
      
    // 放入元素  
    public boolean put(K key,V value){  
        // 获得在数组中的索引值  
        int hash=key.hashCode();  
        Entry<K,V> temp=new Entry(key,value,hash);  
        if(addEntry(temp,table)){  
            size++;  
            return true;  
        }  
        return false;  
    }  
      
    // 增加元素到指定索引处  
    private boolean addEntry(HashTable<K, V>.Entry<K, V> temp,  
            HashTable<K, V>.Entry<K, V>[] table) {  
        //1. 获得索引值  
        int index=indexFor(temp.hash,table.length);  
        //2. 依据索引找到该地位的元素  
        Entry<K,V> entry=table[index];  
        //2.1 非空，则遍历并进行比拟  
        if(entry!=null){while(entry!=null){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;  
                else if(temp.key!=entry.key&&temp.value!=entry.value){if(entry.next==null)  
                        break;  
                    entry=entry.next;  
                }  
            }  
            //2.2 链接在该索引地位处最初一个元素上  
            addEntryLast(temp,entry);  
        }  
        //3. 若空则间接放在该地位  
        setFirstEntry(temp,index,table);  
        //4. 插入胜利，返回 true  
        return true;  
    }  
      
    // 链接元素到指定索引处最初一个元素上  
    private void addEntryLast(HashTable<K, V>.Entry<K, V> temp,  
            HashTable<K, V>.Entry<K, V> entry) {if(size>threshold)  
            reSize(table.length*4);  
        entry.next=temp;  
    }  
  
    // 初始化索引处的元素值  
    private void setFirstEntry(HashTable<K, V>.Entry<K, V> temp, int index,  
            HashTable<K, V>.Entry<K, V>[] table) {if(size>threshold)  
            reSize(table.length*4);  
        table[index]=temp;  
        // 留神指定其 next 元素，避免屡次应用该哈希表时造成抵触  
        temp.next=null;  
    }  
  
    // 扩容容量  
    private void reSize(int newSize) {Entry<K,V> newTable[]=new Entry[newSize];  
        threshold=(int) (loadFactor*newSize);  
        for(int i=0;i<table.length;i++){Entry<K,V> entry=table[i];  
            // 数组中，实际上每个元素都是一个链表，所以要遍历增加  
            while(entry!=entry){addEntry(entry,newTable);  
                entry=entry.next;  
            }  
        }  
        table=newTable;  
    }  
  
  
    // 计算索引值  
    private int indexFor(int hash, int tableLength) {  
        // 通过逻辑与运算，失去一个比 tableLength 小的值  
        return hash&(tableLength-1);  
    }  
      
    // 获得与 key 对应的 value 值  
    protected V get(K k){  
        Entry<K,V> entry;  
        int hash=k.hashCode();  
        int index=indexFor(hash,table.length);  
        entry=table[index];  
        if(entry==null)  
            return null;  
        while(entry!=null){if(entry.key==k||entry.key.equals(k))  
                return entry.value;  
            entry=entry.next;  
        }  
        return null;  
    }  
      
    // 外部类，包装须要存在哈希表中的元素  
    class Entry<K,V>{  
        Entry<K,V> next;  
        K key;  
        V value;  
        int hash;  
          
        Entry(K k,V v,int hash){  
            this.key=k;  
            this.value=v;  
            this.hash=hash;  
        }  
    }  
      
}