数据结构——Hash表

散列表的概念

1、散列表

    　散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。

    　设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。
    　散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。
  其中：
　    ① h：U→{0，1，2，…，m-1} ，通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围，使待处理的|U|个值减少到m个值，从而降低空间开销。
    　② T为散列表(Hash Table)。
    　③ h(K_i)(K_i∈U)是关键字为K_i结点存储地址(亦称散列值或散列地址)。
    　④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing)

2、散列表的冲突现象
（1）冲突
    　两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。
  　【例】上图中的k₂≠k₅，但h(k₂)=h(k₅)，故k₂和K₅所在的结点的存储地址相同。

（2）安全避免冲突的条件
    　最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：
①其一是|U|≤m
②其二是选择合适的散列函数。
　    这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。

（3）冲突不可能完全避免
    　通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。

（4）影响冲突的因素
    　冲突的频繁程度除了与h相关外，还与表的填满程度相关。
    　设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(Load Factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。

3、Java实现

DataItem.java

package zieckey.datastructure.study.hash;

public class DataItem
{
    public int iData;
    public DataItem( int ii )
    {
        iData = ii;
    }
}


package zieckey.datastructure.study.hash;

/**
 *
 * 线形探测
 * 探测过程：x,x+1,x+2,x+3,x+4等，依此类推
 *
 * @author zieckey
 *
 */
public class HashTable_LineProbe
{
    DataItem[]    hashArray;
    int            arraySize;
    DataItem    nonItem;    // 删除的元素


    public HashTable_LineProbe( int size )
    {
        arraySize = size;
        hashArray = new DataItem[size];
        nonItem = new DataItem( -1 );
    }

    // 哈希函数

    public int hashFunc( int key )
    {
        return key % arraySize; // hash function

    }

    public void insert( DataItem item )
    {
        int key = item.iData;
        int hashVal = hashFunc( key );// 找hash表中的序号


        while ( null != hashArray[hashVal] && -1 != hashArray[hashVal].iData )
        {

            if ( hashVal == arraySize - 1 )// 如果是最后一个元素，那么从0开始循环

            {
                hashVal = 0;
            } else
            {
                hashVal++ ;
            }
        }

        // 找到了hash序号

        hashArray[hashVal] = item;

    }
    
    public DataItem delete( int key ) // delete a DataItem

    {
        int hashVal = hashFunc( key ); // hash the key

        while ( hashArray[hashVal] != null ) // until empty cell,

        { // found the key?

            if ( hashArray[hashVal].iData == key )
            {
                DataItem temp = hashArray[hashVal]; // save item

                hashArray[hashVal] = nonItem; // delete item

                return temp; // return item

            }
            
            if ( hashVal == arraySize - 1 )// 如果是最后一个元素，那么从0开始循环

            {
                hashVal = 0;
            } else
            {
                hashVal++ ;
            }
        }
        return null; // can't find item

    } // end delete()

    
    public DataItem find( int key ) // find item with key

    {
        int hashVal = hashFunc( key ); // hash the key

        while ( hashArray[hashVal] != null ) // until empty cell,

        { // found the key?

            if ( hashArray[hashVal].iData == key )
            {
                return hashArray[hashVal]; // yes, return item

            }
            
            if ( hashVal == arraySize - 1 )// 如果是最后一个元素，那么从0开始循环

            {
                hashVal = 0;
            } else
            {
                hashVal++ ;
            }
        }
        return null; // can't find item

    }

    public void displayTable()
    {
        System.out.print( "Table: " );
        for ( int j = 0; j < arraySize; j++ )
        {
            if ( hashArray[j] != null )
                System.out.print( hashArray[j].iData + " " );
            else
                System.out.print( "** " );
        }
        System.out.println( "" );
    }

}


package zieckey.datastructure.study.hash;

/**
 * 二次探测 探测过程：x,x+1,x+4,x+9,x+25等，依此类推
 *
 * @author zieckey
 */
public class HashTable_QuadraticProbe
{
    DataItem[]    hashArray;
    int            arraySize;
    DataItem    nonItem;    // 删除的元素


    public HashTable_QuadraticProbe( int size )
    {
        arraySize = size;
        hashArray = new DataItem[size];
        nonItem = new DataItem( -1 );
    }

    // 哈希函数

    public int hashFunc( int key )
    {
        return key % arraySize; // hash function

    }

    public void insert( DataItem item )
    {
        int key = item.iData;
        int hashVal = hashFunc( key );// 找hash表中的序号


        int tempHashVal = hashVal;
        System.out.print("indexHash = ");
        for ( int i = 1; null != hashArray[tempHashVal]
                && -1 != hashArray[tempHashVal].iData; i++ )
        {
            System.out.print(tempHashVal + " ");
            tempHashVal = hashVal + i * i;
            tempHashVal = tempHashVal % arraySize;
            
            /**
             * 该情况下，表明一直在寻找一个合适的index，却在循环，
             * 例如，arraySize=20，多次插入183，
             * 最后的结果就是index=3 4 7 12 19 8 19 12 7 4 3 4 7 12 19 8 19 12 7 4 3
             */
            if ( i>arraySize )
            {
                System.out.println("");
                System.out.println("There is no cell for this DataItem.");
                return;
            }
            
        }
        System.out.print(tempHashVal + " ");
        System.out.println("");
    
        // 找到了hash序号

        hashArray[tempHashVal] = item;

    }

    public DataItem delete( int key ) // delete a DataItem

    {
        int hashVal = hashFunc( key ); // hash the key

        int tempHashVal = hashVal;

        for ( int i = 1; hashArray[tempHashVal] != null; i++ )
        { // found the key?

            if ( hashArray[tempHashVal].iData == key )
            {
                DataItem temp = hashArray[tempHashVal]; // save item

                hashArray[tempHashVal] = nonItem; // delete item

                return temp; // return item

            }
            
            tempHashVal = hashVal + i * i;
            tempHashVal = tempHashVal % arraySize;
        }

        return null; // can't find item

    } // end delete()


    public DataItem find( int key ) // find item with key

    {
        int hashVal = hashFunc( key ); // hash the key

        int tempHashVal = hashVal;
        
        for ( int i=1;hashArray[tempHashVal] != null;i++ ) // until empty cell,

        { // found the key?

            if ( hashArray[tempHashVal].iData == key )
            {
                return hashArray[tempHashVal]; // yes, return item

            }

            tempHashVal = hashVal + i * i;
            tempHashVal = tempHashVal % arraySize;
        }
        return null; // can't find item

    }

    public void displayTable()
    {
        System.out.print( "Table: " );
        for ( int j = 0; j < arraySize; j++ )
        {
            if ( hashArray[j] != null )
                System.out.print( hashArray[j].iData + " " );
            else
                System.out.print( "** " );
        }
        System.out.println( "" );
    }

}