数据结构——Hash表

zieckey

散列表的概念
               
                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(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。

                    　④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing)
2、散列表的冲突现象
                [color="#0000ff"] （1）冲突
                    　两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。
                  　【例】上图中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。
               
                [color="#0000ff"]（2）安全避免冲突的条件
                    　最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：
                ①其一是|U|≤m
                ②其二是选择合适的散列函数。
            　    这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。

               

                [color="#0000ff"] （3）冲突不可能完全避免

                    　通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。
               
                [color="#0000ff"] （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( "" );
    }
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/16292/showart_528388.html