hash map

hash.txt

1.hash 通过函数h将输入映射到一个固定的位置，h(i) = position,最简单的hash函数就是 h(i) = i mod Table_Size
2.Table_Size最好就是一个素数
3.hash就一定会有碰撞，常用的方法open address法，即当发生碰撞的时候，如何寻找下一个空位（装填因子应该小于0.5）。
 1.线性探测。F(i)=i,发生碰撞之后，探测发生碰撞位置的下一个是否为空。缺点，形成区块聚堆
 2.平方探测法。F(i)=i^2,发生碰撞之后，按照1，4，9，16这样的距离寻找空位
3.使用open address法，当装填太多的时候，效率会降低。这个时候需要rehash，将table扩容，对原来的数据全部再hash一次。
4.常用hash函数(http://blog.csdn.net/jason5186/article/details/9037623)

hash table主要函数
1.insert
/**
 *  插入一个元素
 *  @param input 要插入的元素
 */
hash_insert (input)
{
    i = 0;
    while(i != array_size)
    {
        j = HASH(input , i , array_size); // 取出位置
        if(status_array_ptr[j] != FULL) // 判别元素是否是开放为空的
        {
            array_ptr[j] = t;   //插入元素
            status_array_ptr[j] = FULL;//并将该位置状态设为已经被插入
            return true;
        }
        ++i;
    }
    return false;
} 

2.search
/*
 * 查找元素
 * @param input      要查找的键值
 * @param target 返回找到的目标
 */
hash_search (input , target)
{
    i = 0;
    while(i != array_size)
    {
        size_t j = HASH(input , i , array_size) ;
        if(status_array_ptr[j] == EMPTY) // 之后就再也没有元素了
            return false;
        else if (status_array_ptr[j] == FULL)
        {
            if(array_ptr[j].key == t.key )  
            {
                target = array_ptr[j];
                return true;
            }
        }
        ++i;
    }
    target = T();
    return false;
}

3.delete
/**
 *  插入一个元素
 *  @param input 要插入的元素
 */
hash_delete (input)
{
    i = 0;   
    while(i != array_size)
    {
        j = HASH(input , i , array_size);
        if(status_array_ptr[j] == EMPTY)
            return false;
        else if (status_array_ptr[j] == FULL)
        {
            if(array_ptr[j].key == t.key )  
            {
                status_array_ptr[j] = DELETED;// 不应该是EMPTY
                return true;
            }
        }
        ++i;
    }
    return false;
}