算法学习笔记(三)——散列表

1.1 散列表(哈希表)

  散列表(哈希表)是根据键值而直接进行访问的数据结构。通过一个散列函数将查找的键转换为表中的一个索引,来加快查找的速度。理想情况下,不同的键值都能转化为不同的索引值,但是在现实中,我们常常要处理多个键值对应同一个索引值。所以,散列查找的算法分为两个部分。第一部分就是关键的散列函数,第二部分就是处理哈希冲突。

1.2 散列函数

  散列函数就是通过该函数将元素的键值转换为表的索引。散列函数应该易于计算并且能够均匀分布所有的键,得到的散列值应该是一个非负整数,每个不同的键都有一一对应的散列值。

1.3 哈希冲突的处理

  1. 拉链法

    将表的每一个索引位置都对应一个链表,链表的每个结点都存储了对应的键值。

  2. 开放地址法

    用大小为M的数组保存N个键值对(M>N),通过依靠数组中的空位解决哈希冲突。最简单的开放地址法便是线性探测法,当碰撞发生时,我们直接检查散列表的下一个位置。此时可能有三种结果,命中,未命中或者继续查找。

2.代码实现

  1. 基于拉链法实现的散列表

    template <typename key, typename value>
    class ChainingListHashTable
    {
    private:
        int N;      //键值对数量
        int M;      //散列表的大小
        vector<vector<value>> List;
    
        int MyHash(key key)
        {
            hash<key> hash_key;
            return (hash_key(key) & 0x7ffffff % M);
        }
    public:
        ChainingListHashTable(int m)
        {
            N = 0;
            M = m;
            List.resize(m);
        }
        
        value get(key key)
        {
            return List[MyHash(key)][0];
        }
    
        void put(key key, value value)
        {
            List[MyHash(key)].push_back(value);
            N++;
        }
        
        void erase(key key)
        {
            value v = MyHash(key);
            for(int i = 0; i < List[v].size(); ++i)
            {
                if(List[v][i]==key)
                {
                    List[v].erase(List[v].begin()+i);
                    return;
                }    
            }
            cerr<<"No such key in List"<<endl;
            return;
        }
    };
    
  2. 基于线性探测法的散列表

    template <typename key, typename value>
    class LinearProbingHashTable
    {
    private:
        int N;
        static int M = 16;
        vector<key> keys;
        vector<value> values;
        int MyHash(key key)
        {
            hash<key> hash_key;
            return (hash_key(key) & 0x7ffffff % M);
        }
        void resize(int cap)
        {
            keys.resize(cap);
            values.resize(cap);
        }
    
        bool contains(key key)
        {
            for (int i = MyHash(key); keys[i] != NULL; i = (i + 1) % M)
            {
                if (keys[i] == key)
                    eturn true;
            }
            return false;
        }
    
    public:
        LinearProbingHashTable()
        {
            keys.resize(M);
            values.resize(M);
        }
    
        void put(key key, value value)
        {
            if (N >= M / 2)
                resize(2 * M);
            int i;
            for (i = MyHash(key); keys[i] != NULL; i = (i + 1) % M)
            {
                if (keys[i] == key)
                {
                    values[i] = value;
                    return;
                }
            }
            keys[i] = key;
            values[i] = value;
            N++;
        }
    
        value get(key key)
        {
            for (int i = MyHash(key); keys[i] != NULL; i = (i + 1) % M)
            {
                if (keys[i] == key)
                    return values[i];
            }
            return NULL;
        }
    
        void erase(key Key)
        {
            if (!contains(Key))
                return;
            int i = MyHash(Key);
            while (keys[i] != Key)
                i = (i + 1) % M;
            keys[i] = NULL;
            values[i] = NULL;
            i = (i + 1) % M;
            while (keys[i] != NULL)
            {
                key keyToRedo = keys[i];
                value valueToRedo = values[i];
                keys[i] = NULL;
                values[i] = NULL;
                N--;
                put(keyToRedo, valueToRedo);
                i = (i + 1) % M;
            }
            if (N > 0 && N == M / 8)
                resize(M / 2);
        }
    };
    
上一篇:APP自动化-无法清空输入框默认值继续输入


下一篇:Rest Template 常见错误