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

本文由乐趣区整理发布,转载请注明出处,谢谢。

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据