精华内容
下载资源
问答
  • 用java写的拉链法实现哈希表的建立,应用到类似于电话本查询的程序里,课程设计时候做的,所以不是很完美
  • //创建哈希表 int HashTableInsert(HashTable* ht, KeyType key, ValueType value); //插入 HashNode* HashTableFind(HashTable* ht, KeyType key); //查找 int HashTableRemove(HashTable* ht, KeyType key)...
    #include<malloc.h>
    #include<assert.h>
    #include<string.h>
    typedef int KeyType;
    typedef int ValueType;
    typedef struct HashNode
    {
        KeyType _key;
        ValueType _value;
        struct HashNode* _next;
    }HashNode;
    typedef struct HashTable
    {
        HashNode** _tables;
        size_t _size;
        size_t _N;
    }HashTable;
    HashNode* BuyHashNode(KeyType key, ValueType value);//创建一个节点
    size_t HashFunc(KeyType key, size_t N);//查找哈希位置
    size_t Get_Next_Prime_Num(size_t cur_num);//素数表
    void Check_Capacity(HashTable* ht);//检查容量
    void HashTableInit(HashTable* ht);//创建哈希表
    int HashTableInsert(HashTable* ht, KeyType key, ValueType value);//插入
    HashNode* HashTableFind(HashTable* ht, KeyType key);//查找
    int HashTableRemove(HashTable* ht, KeyType key);//删除
    void HashTableDestory(HashTable* ht);//销毁表
    
    HashNode* BuyHashNode(KeyType key, ValueType value)
    {
        HashNode* node = (HashNode*)malloc(sizeof(HashNode));
        assert(node);
        node->_key = key;
        node->_value = value;
        node->_next = NULL;
        return node;
    }
    size_t HashFunc(KeyType key, size_t N)
    {
        return key % N;
    }
    size_t Get_Next_Prime_Num(size_t cur_num)//素数表
    {
        const int _PrimeSize = 28;
        static const unsigned long _PrimeList[_PrimeSize] = {
            53ul,         97ul,         193ul,       389ul,       769ul,
            1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
            49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
            1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
            50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
            1610612741ul, 3221225473ul, 4294967291ul
        };
        for (size_t i = 0; i < _PrimeSize; i++)
        {
            if (cur_num < _PrimeList[i])
            {
                return _PrimeList[i];
            }
        }
        return _PrimeList[_PrimeSize - 1];
    }
    void HashTableInit(HashTable* ht)
    {
    
        ht->_tables = (HashNode**)malloc(sizeof(HashNode*) * Get_Next_Prime_Num(0));
        assert(ht->_N);
        ht->_N = Get_Next_Prime_Num(0);
        ht->_size = 0;
        memset(ht->_tables, NULL, sizeof(HashNode*) * ht->_N);
    }
    void Check_Capacity(HashTable* ht)
    {
        if (ht->_size > ht->_N)
        {
            HashTable newht;
            newht._tables = (HashNode**)malloc(sizeof(HashNode*)*Get_Next_Prime_Num(ht->_N));
            newht._N = Get_Next_Prime_Num(ht->_N);
            memset(newht._tables, NULL, sizeof(HashNode*) * newht._N);
            for (size_t i = 0; i < newht._N; i++)
            {
                HashNode* cur = newht._tables[i];
                while (cur)
                {
                    size_t Nnewindex = HashFunc(cur->_key, newht._N);
                    cur->_next = newht._tables[i];
                    cur = cur->_next;
                }
            }
            free(ht->_tables);
            ht->_N = newht._N;
            ht->_tables = newht._tables;
        }
    }
    int HashTableInsert(HashTable* ht, KeyType key, ValueType value)
    {
    
        size_t index = HashFunc(key, ht->_N);
        if (ht->_tables[index] == NULL)
        {
            ht->_tables[index] = BuyHashNode(key, value);
            ht->_size++;
            return 0;
        }
        Check_Capacity(ht);
        HashNode* cur = ht->_tables[index];
        while (cur)
        {
            if (cur->_key == key)
            {
                return -1;
            }
            cur = cur->_next;
        }
        //头插
        HashNode *node = BuyHashNode(key, value);
        node->_next = ht->_tables[index];
        ht->_tables[index] = node;
        ++ht->_size;
        return 0;
    }
    HashNode* HashTableFind(HashTable* ht, KeyType key)
    {
        size_t index = HashFunc(key, ht->_N);
        HashNode* cur = ht->_tables[index];
        while (cur)
        {
            if (cur->_key == key)
            {
                return cur;
                break;
            }
            cur = cur->_next;
        }
        return NULL;
    }
    int HashTableRemove(HashTable* ht, KeyType key)
    {
        size_t index = HashFunc(key, ht->_N);
        HashNode* cur = ht->_tables[index];
        if (cur->_key == key)
        {
            cur = cur->_next;
            free(cur);
            return 1;
        }
        else
        {
            HashNode* tmp = cur;
            cur = cur->_next;
            while (cur)
            {
                if (cur->_key == key)
                {
                    tmp->_next = cur->_next;
                    free(cur);
                    return 1;
                }
                tmp = cur;
                cur = cur->_next;
            }
            return -1;
        }
    }
    void HashTableDestory(HashTable* ht)
    {
        for (size_t i = 0; i < ht->_N; i++)
        {
            HashNode* cur = ht->_tables[i];
            while (cur)
            {
                HashNode* tmp = cur;
                cur = cur->_next;
                free(tmp);
            }
        }
        free(ht->_tables);
        ht->_N = 0;
        ht->_size = 0;
    }
    
    void Printhas(HashTable* ht)
    {
        for (size_t i = 0; i < ht->_N; i++)
        {
            HashNode* cur = ht->_tables[i];
            while (cur)
            {
                printf("%d->",cur->_key);
                cur = cur->_next;
            }
            printf("\n");
        }
    }
    展开全文
  • 一、简介为了解决线性探构造哈希表所出现的大量哈希冲突,我们采用了另外一种方法,便是开链法。而在SGI版本的STL中调用的也正是哈希桶的实现方法。...二、拉链法实现原理:采用了由N个头指针构成的

    一、简介

    为了解决线性探构造哈希表所出现的大量哈希冲突,我们采用了另外一种方法,便是开链法。而在SGI版本的STL中调用的也正是哈希桶的实现方法。

    注意:

    开链法实现哈希表的时候会出现很多很多的错误,比如各种模板错误,此时需要耐心,慢慢调整。同时又为了扩展hash_map与hash_set更改了一些模板参数,所以经过调试错误的过程,绝对会对模板有一个全新的认识。

    二、拉链法实现原理:

    采用了由N个头指针构成的数组,在每个表格内部维护一个List,经过哈希函数的计算,我们可以得到某一个List,我们所做的插入删除和查找等操作全部位于这个LIst上。

    我们需要注意的是虽然List的遍历是线性的,但是如果List足够短,我们操作起来速度还是很快。

    这里写图片描述

    三、拉链法优缺点

    优点:

    1. 解决了线性探测所导致的太多的哈希冲突。
    2. 删除结点相比于开放定址法更容易实现(在线性探测中如果删除结点,后面的结点无法访问)。
    3. 搜索的时间下降

    缺点:

    1. 如果相同元素过多,元素在一个桶内部链接过长,反而导致时间复杂度上升。解决思路是桶中元素不再指向链表,而指向一个红黑树

    四、拉链法实现

    哈希表里面存放一个链表的指针,和一个判断的数据。可以把哈希表中的元素看作链表的第一个结点,类似于指针数组。

    链表里面包含指向下一个结点的指针,数据tata,结点构造如下:

    template <class ValueType>
    struct HashNode
    {
        ValueType _valueField;
    
        HashNode* _next;
    
        HashNode(const ValueType& valueField)
            :_valueField(valueField)
            , _next(NULL)
        {}
    };

    hashtable数据结构

    插入

    第一步:检查容量是否需要扩容。
    第二步:查看此时的key所对应的哈希桶位置。
    第三步:构造出新的结点。
    第四步:找到此哈希桶位置所链接的List所对应的结点,如果存在则插入失败,不存在则插入,此时采用头插法(头插只需要考虑结点为空和不为空,但是可以直接处理)。

    查找

    第一步:找到此key所对应的哈希桶的位置。
    第二步:进入此哈希桶所指向的List查看Key是否相同即可。

    删除

    类似链表删除,定义两个指针,指向前后两个元素。

    第一步:找到key所对应的哈希桶的位置。
    第二步:定义两个指针,一个是需要删除的指针,一个是它前一个指针。
    判断两种情况

    • 情况一:要删除结点为链表的头结点
    • 情况二:删除结点为其他结点。

    第三步:分以上两个结点的情况删除即可。

    负载因子判别

    size如果等于——table的size,增容时也可以选择重新哈希结点来构造新的哈希表,但是这样做时间复杂度很高,所以我们采用现代的写法。

    现代写法是:

    1. 创建新表,resize获取容量。
    2. 遍历原表把整个结点摘下来,先保存上一个结点,接着拿结点。
    3. 找到新表的插入地方,采用头插法插入结点

    析构函数

    析构函数必须写,因为挂的是结点。
    方法:
    查找整个vector如果其中哈希桶不为0,则析构掉所链接的链表所有元素,如果为NULL则跳出循环即可。

    template <class K>
    struct _HashFunc
    {
        size_t operator()(const K& key)
        {
            return key%_t;
        }
    };
    //sting的单独版本
    template <>
    struct _HashFunc<string> //特化string类型的仿函数
    {
        static size_t BKDRHash(const char * str)
        {
            unsigned int seed = 131; // 31 131 1313 13131 131313
            unsigned int hash = 0;
            while (*str)
            {
                hash = hash * seed + (*str++);
            }
            return (hash & 0x7FFFFFFF);
        }
    
        size_t operator()(const string& key)
        {
            return BKDRHash(key.c_str());
        }
    };
    
    template <class ValueType>
    struct HashNode
    {
        ValueType _valueField;
    
        HashNode* _next;
    
        HashNode(const ValueType& valueField)
            :_valueField(valueField)
            , _next(NULL)
        {}
    };
    
    template <class K, class V, class Hashfunc = _HashFunc<K> >
    class HashTable
    {
        typedef V ValueType;
        typedef HashNode<ValueType> Node;
    public:
        HashTable()
            :_size(0)
        {
            _tables.resize(_GetPrime(0));
        }
        HashTable(const HashTable& Hash)
        {
            _Copy();
        }
        ~HashTable()
        {
            Node* del = NULL;
            Node* cur = NULL;
            for (size_t i = 0; i < _tables.size(); ++i)
            {
                cur = _tables[i];
                while (cur)
                {
                    del = cur;
                    delete del;
                    del == NULL;
                    cur = cur->_next;
                }
            }
        }
        bool Insert(const ValueType& valueField)
        {
            _checkcapcity();
            size_t index = Hashfunc(key);
    
            Node* NewNode = new Node(valueField);
            if (_tables[index])
            {
                Node* cur = _tables[index];
                while (cur)
                {
                    if (cur->_valueField == valueField)
                        return false;
                    cur = cur->_next;
                }
            }
            ++_size;
            NewNode->_next = _tables[index];
            _tables[index] = NewNode;
            return true;
        }
        Node* Find(const K& key)
        {
            size_t index = Hashfunc(key);
            Node* cur = _tables[index];
            while (cur)
            {
                if (cur->_valueField==key)
                    return cur;
                cur = cur->_next;
            }
            return NULL;
        }
        bool Rremove(const K& key)
        {
            size_t index = Hashfunc(key);
            Node* cur = _tables[index];
            Node* prev = NULL;
            Node* del = NULL;
            while (cur)
            {
                if (cur->_valueField == key)
                {
                    if (prev == NULL)
                    {
                        del = cur;
                        delete del;
                        _tables[index] == NULL;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                        delete cur;
                    }
                    --_size;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return true;
        }
    protected:
        int _HashFunc(const K& key)
        {
            if (_tables.size())
            {
                return HashFunc()(key) % _tables.size();
            }
            return -1;
        }
        void _checkcapcity()
        {
            if (_size * 10 == table._size() || __tables.size() == 0)
            {
                HashTable<K, V, HashFunc> hash;
                size_t NewSize = _GetPrime(_tables.size());
                hash._tables.resize(NewSize);
                Node* cur = NULL;
                Node* NewNode = NULL;
    
                for (size_t i = 0; i < _tables.size(); i++)
                {
                    cur = _tables[i];
                    if (cur == NULL)
                        continue;
                    while (cur)
                    {
                        size_t newpos = Hashfunc(cur->_valueField);
                        NewNode = cur;
                        cur = cur->_next;
                        NewNode->_next = hash._tables[newpos];
                        hash._tables[newpos] = NewInsert;
                    }
    
                    _tables[i] = NULL;
    
                }
                Swap(hash);
            }
    
        }
        static unsigned _GetPrime(const unsigned long size)
        {
            const int _PrimeSize = 28;
            static const unsigned long _PrimeList[_PrimeSize] =
            {
                53ul, 97ul, 193ul, 389ul, 769ul,
                1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
                49157ul, 98317ul, 196613ul, 393241ul,
                786433ul,
                1572869ul, 3145739ul, 6291469ul, 12582917ul,
                25165843ul,
                50331653ul, 100663319ul, 201326611ul, 402653189ul,
                805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
            //以下查找比当前数还要大的素数
            for (size_t i = 0; i < _PrimeSize; i++)
            {
                if (size < _PrimeList[i])
                    return _PrimeList[i];
            }
            //没找到就返回最后一个数
            return _PrimeList[_PrimeSize - 1];
        }
        Node* Swap(HashTable<K, V, HashFunc>& table)
        {
            if (*this != table)
            {
                _table.swap(table._tables);
                swap(_size, table._size);
            }
        }
    private:
        vector<Node*> _tables;
        size_t _size;
    };
    展开全文
  • 哈希表拉链法

    千次阅读 2018-03-10 20:14:11
    > 开散列又叫链地址(开链... 桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 设元素的关键码为37, 25, 14, 36, 49, 68, 57, 11, 散列表为HT[12],表的大小为12,散列函数为Hash(x) = x % 11

    > 开散列法又叫链地址法(开链法)。

    开散列法:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个
    桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    设元素的关键码为37, 25, 14, 36, 49, 68, 57, 11, 散列表为HT[12],表的大小为12,散列函数为Hash(x) = x % 11
    Hash(37)=4
    Hash(25)=3
    Hash(36)=3
    Hash(49)=5
    Hash(68)=2
    Hash(11)=0
    使用哈希函数计算出每个元素所在的桶号,同一个桶的链表中存放哈希冲突的元素。
    通常,每个桶对应的链表结点都很少,将n个关键码通过某一个散列函数,存放到散列表中的m个桶中,那么每一个桶中链表的平均 长度为 。以搜索平均长度为 的链表代替了搜索长度为 n 的顺序表,搜索效率快的多。
    应用链地址法处理溢出,需要增设链接指针,似乎增加了存储开销。事实上: 由于开地址法必须保持大量的空闲空间以确保搜索效率,如二次探查法要求装载因子a <= 0.7,而表项所占空间又比指针大的多, 所以使用链地址法反而比开地址法节省存储空间。

    开散列的实现(拉链法)
    HashNode.h

    #pragma once
    #include <stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    typedef int KeyType;
    typedef int valueType;
    typedef struct HashNode
    {
        KeyType _key;
        valueType _value;
        struct HashNode*_next;
    }HashNode;
    typedef struct HashTable
    {
        HashNode** table;
        size_t _size;
        size_t _N;
    }HashTable;
    HashNode*BuyHashNode(KeyType key, valueType value);
    size_t GetHashTablePrime(size_t N);
    void HashTableInit(HashTable*ht,int size);//初始化
    void HashTablePrint(HashTable*ht);
    int HashTableInsert(HashTable*ht, KeyType key, valueTypevalue);//
    HashNode* HashTableFind(HashTable*ht, KeyType key);//查找
    size_t HashTableErase(HashTable*ht, KeyType key);//删除
    void HashTableDesTroy(HashTable*ht);//销毁
    

    HashNode.c

    #include"HashNode.h"
    HashNode* BuyHashNode(KeyType key, valueType value)
    {
        HashNode*Node = (HashNode*)malloc(sizeof(HashNode));
        assert(Node);
        Node->_key = key;
        Node->_value = value;
        Node->_next = NULL;
        return Node;
    }
    void HashTableInit(HashTable*ht,int size)//初始化
    {
        assert(ht);
        ht->_size = 0;
        ht->_N = size;
        //这里要注意开辟空间是给指针数组
        ht->table = (HashTable**)malloc(sizeof(HashTable*)*ht->_N);
        assert(ht->table);
        memset(ht->table, 0, sizeof(HashTable*)*ht->_N);
    }
    size_t GetHashTablePrime(size_t N)
    {
        static const unsigned long _PrimeList[28] =
            {
                53ul, 97ul, 193ul, 389ul, 769ul,
                1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
                49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
                1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
                50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
            for (int i = 0; i < 28; i++)
            {
                if (N < _PrimeList[i])
                {
                    N = _PrimeList[i];
                    return N;
                }
    
            }
            return _PrimeList[27];
    
    
    }
    size_t HashFunc(KeyType key, size_t N)
    {
        return key%N;
    }
    
    int HashTableInsert(HashTable*ht, KeyType key, valueType value)//插入
    {
    
        assert(ht);
        HashNode* node = BuyHashNode(key, value);
        if (ht->_size * 10 / ht->_N > 7)
        {
            //扩容
            size_t newN = GetHashTablePrime(ht->_N);
            HashTable newht;
            HashTableInit(&newht, newN);
    
            for (size_t i = 0; i < ht->_N; i++)
            {
                HashNode* cur = ht->table[i];//得到链表表头节点的地址
                if (ht->table[i])
                {
                    size_t index = HashFunc(cur->_key, newht._N);//重新计算原表中的值在新表中的位置
                    while (cur)
                    {
                        cur->_next = newht.table[index];//将原表头节点的下一个指向新表头结点
                        newht.table[index] = cur;//原表头结点赋给新表头结点实现原表值映射到新表中
                        cur = cur->_next;
                    }
    
                }
            }
            free(ht->table);
            ht->_N = newN;//将新表中的扩容给旧表
            ht->table = newht.table;//新表赋给原表
        }
    
        size_t index = HashFunc(key, ht->_N);
        if (ht->table[index])
        {
            HashNode*cur = ht->table[index];
            while (cur)
            {
                if (cur->_key == key)
                {
                    return -1;
                }
                cur = cur->_next;
            }
    
        }
        node->_next = ht->table[index];
        ht->table[index] = node;
        ht->_size++;
        return 0;
    }
    void HashTablePrint(HashTable*ht)
    {
        for (size_t i = 0; i < ht->_N; i++)
        {
            if (ht->table[i])
            {
                HashNode*cur = ht->table[i];
                while (cur)
                {
                    printf("[%d]->%d\n ",i, cur->_key);
                    cur = cur->_next;
                }
    
            }
        }
    }
    HashNode *HashTableFind(HashTable*ht, KeyType key)
    {
        assert(ht);
        size_t index = HashFunc(key, ht->_N);
        if (ht->table[index])
        {
            if (ht->table[index]->_key=key)
            {
                return ht->table[index];
            }
            else
            {
                HashNode*cur = ht->table[index];
                    while (cur)
                    {
                        if (cur->_key==key)
                        {
                            return cur;
                        }
                        cur = cur->_next;
                    }
                    return NULL;
            }
        }
    }
    size_t HashTableErase(HashTable*ht, KeyType key)
    {
        assert(ht);
        size_t index = HashFunc(key, ht->_N);
        if (ht->table[index])
        {
            HashNode* cur = ht->table[index];
            HashNode* prev = ht->table[index];
            while (cur)
            {
                if (cur == prev&&cur->_key == key)//只有一个节点
                {
                    ht->table[index] = cur->_next;
                    free(cur);
                    cur = NULL;
                    ht->_size--;
                    return 0;
                }
                else if (cur->_key == key)//多个节点
                {
                    prev = cur->_next;
                    free(cur);
                    cur = NULL;
                    ht->_size--;
                    return 0;
                }
                prev = cur;
                cur = cur->_next;
            }
            return -1;
        }
    
        else
        {
            return -1;
        }
    }
    void HashTableDesTroy(HashTable*ht)
    {
        assert(ht);
        for (size_t i = 0; i < ht->_N; i++)
        {
            if (ht->table[i])
            {
                HashNode*cur = ht->table[i];
                while (cur)
                {
                    HashNode*tmp = cur;
                    cur = cur->_next;
                    free(tmp);
                    tmp = NULL;
    
                }
            }
        }
        free(ht->table);
        ht->table = NULL;
        ht->_N = 0;
        ht->_size = 0;
    }

    test.c

    #include"HashNode.h"
    void test()
    {
        HashTable ht;
        HashTableInit(&ht,5);
        HashTableInsert(&ht, 8,0);
        HashTableInsert(&ht, 11, 0);
        HashTableInsert(&ht, 10, 0);
        HashTableInsert(&ht, 12, 0);
        HashTableInsert(&ht, 2, 0);
        HashTableInsert(&ht, 5, 0);
        HashTableInsert(&ht, 20, 0);
        HashTablePrint(&ht);
        printf("\n");
    
        printf("%d\n ", HashTableFind(&ht, 10)->_key);
        printf("%d\n ", HashTableFind(&ht, 12)->_key);
        printf("%d\n ",HashTableFind(&ht, 20)->_key);
        printf("%d\n", HashTableFind(&ht, 8)->_key);
        printf("%p\n ", HashTableFind(&ht, 1)->_key);
        printf("\n");
        HashTableErase(&ht, 8);
        HashTableErase(&ht, 2);
        HashTableErase(&ht, 5);
        HashTableErase(&ht, 20);
        HashTablePrint(&ht);
        printf("\n");
        HashTableDesTroy(&ht);
        HashTablePrint(&ht);
    
    
    }
    int main()
    {
        test();
        system("pause");
        return 0;
    }
    展开全文
  • 2.哈希表拉链法实现 2.1完全由本人思路实现,如有错误,欢迎批评指正 哈希声明文件hash.h /* 哈希表 * by : I'M渣渣 * date: 2021.5.11 */ #ifndef __HASH_H_ #define __HASH_H_ #define size 100 //哈希数组大小...

    C语言哈希表的简单实现——数组+链表(拉链法)

    1.哈希表简介

    哈希表详细介绍可以参考这篇文章

    2.哈希表拉链法实现

    2.1完全由本人思路实现,如有错误,欢迎批评指正

    哈希声明文件hash.h

    /* 哈希表
    *  by  : I'M渣渣
    *  date: 2021.5.11
    */
    
    #ifndef __HASH_H_
    #define __HASH_H_
    
    #define size 100  //哈希数组大小为100
    #include <stdbool.h> //C语言使用bool类型需要调用的头文件
    #include <stdio.h>
    #include <stdlib.h>
    
    //创建哈希结构体
    typedef struct hash_value_{
        int _int_key;
        double _double_key;
        float _float_key;
        char _char_key;
        char *_str_key;
    
        int _int;
        double _double;
        float _float;
        char _char;
        char *_str;
    
        struct hash_value_ * _hash_value_next;
    }hash_value;
    //创建hash_value指针数组
    hash_value *hash_arry[size];
    
    void hash_default(hash_value *hash_arry_[]); //哈希数组初始化
    int hash_int(int key); 
    int hash_double(double key);          //哈希函数
    int hash_float(float key);
    int hash_char(char key);
    int hash_charstr(char *key);
    bool add_mod_key_value_int(int key,int value); //添加与修改 <int key,int value>
    int get_key_value_int(int key); //获取value <int key>
    bool add_mod_key_value_charstr_int(char *key,int value);//添加与修改 <str key,int value>
    int get_key_value_charstr_int(char *key);//获取value <str value>
    #endif // !__HASH_H_
    

    哈希实现hash.c

    /* 哈希表
    *  by  : I'M渣渣
    *  date: 2021.5.11
    */
    #include "hash.h"
    #include "string.h"
    
    //初始化指针数组,全部赋值为空
    void hash_default(hash_value *hash_arry_[]){
        for(int i=0;i<size;++i){
            hash_arry_[i]=NULL;
        }
    }
    
    //创建哈希函数,返回哈希值
    int hash_int(int key){
        return key%size;
    }
    int hash_double(double key){
        return (int)key%size;
    }
    int hash_float(float key){
        return (int)key%size;
    }
    int hash_char(char key){
        return (int)key%size;
    }
    int hash_charstr(char *key){
        int x=0;
        int i=0;
        while(*(key+i)!='\0'){
            x=x+(int)(*key);
            i++;
        }
        return x%size;
    }
    
    //添加操作
    bool add_mod_key_value_int(int key,int value){
        hash_value *head=hash_arry[hash_int(key)];
        hash_value *p=NULL;
        while(head){
            if(key==head->_int_key){
                head->_int=value;
                break;
            }
            if(head->_hash_value_next==NULL) break; 
            if(key>head->_int_key&&key<head->_hash_value_next->_int_key) break;
            
            head=head->_hash_value_next;
        }
        
        hash_value *V=(hash_value *)malloc(sizeof(hash_value));
        if(head==NULL) {
            V->_int_key           = key;
            V->_int               = value;
            V->_hash_value_next   = NULL;//这里为初始指针赋值,初始数组里初始为NULL,不能用head
            hash_arry[hash_int(key)]=V;
        }
        else {
            V->_int_key           = key;
            V->_int               = value;
            
            p                     = head->_hash_value_next;
            head->_hash_value_next= V;
            V->_hash_value_next   = p;  
            
        } 
        return true;
    }
    //获取value值
    int get_key_value_int(int key){
        int *x;
        x=(int *)malloc(2*sizeof(int));
        hash_value *head=hash_arry[hash_int(key)];
        while(head){
            if(key==head->_int_key){
                return head->_int;
            } 
            if(key>head->_int_key&&key<head->_hash_value_next->_int_key){
                return -1;
            }
            head=head->_hash_value_next;
        }
        return -1;
    }
    
    bool add_mod_key_value_charstr_int(char *key,int value){
        hash_value *head=hash_arry[hash_charstr(key)];
        hash_value *p=NULL;
        while(head){
            if(strcmp(key,head->_str_key)){
                head->_int=value;
                break;
            }
            if(head->_hash_value_next==NULL) break; 
            
            
            head=head->_hash_value_next;
        }
        
        hash_value *V=(hash_value *)malloc(sizeof(hash_value));
        if(head==NULL) {
            V->_str_key           = key;
            V->_int               = value;
            V->_hash_value_next   = NULL;
            hash_arry[hash_charstr(key)]=V;
        }
        else {
            V->_str_key           = key;
            V->_int               = value;
            
            p                     = head->_hash_value_next;
            head->_hash_value_next= V;
            V->_hash_value_next   = p;  
            
        } 
        return true;
    }
    int get_key_value_charstr_int(char *key){
        int *x;
        x=(int *)malloc(2*sizeof(int));
        hash_value *head=hash_arry[hash_charstr(key)];
        while(head){
            if(strcmp(key,head->_str_key)==0){
                return head->_int;
            }
            head=head->_hash_value_next;
        }
        return -1;
    }
    

    测试文件main.c

    /* 哈希表
    *  by  : I'M渣渣
    *  date: 2021.5.11
    */
    #include "hash.h"
    #include "stdio.h"
    
    int main(int argc,char *argv[]){
        int arry_key[10000];
        int arry[10000];    
        char *arrystr[10]={//字符串一定要用,号隔开
            "agcdef",
            "dasdawenei",
            "liasdawxuan",
            "apple",
            "yiyaasdwen",
            "asdwert",
            "laasdnshasdu",
            "chenchegfhfghng",
            "qwe",
            "rrrr",
        };
        int arrystrint[10];
        hash_default(hash_arry);
        printf("**********\n");
        /*for(int i=0;i<10000;++i){
            arry_key[i]=i;
            arry[i]=i;
            add_mod_key_value_int(arry_key[i],arry[i]);
        }
        
        
        while (1)
        {
            int x;
            scanf("%d",&x);
            printf("key:%d,value:%d\n",x,get_key_value_int(x));
        }*/
        printf("**********\n");
        for(int i=0;i<10;++i){
            arrystrint[i]=i;
            //printf("\n%s",*(arrystr+i));
            add_mod_key_value_charstr_int(*(arrystr+i),arrystrint[i]);
            //printf("&&&\n");
        }
        printf("**********\n");
        while (1)
        {
            char x[1024];//字符串键入要有一定的内存大小,不能char *x
            scanf("%s",x);
            //printf("%s",x);
            printf("key:%s,value:%d\n",x,get_key_value_charstr_int(x));
        }
    
        return 0;
    }
    
    展开全文
  • C++拉链法构造哈希表

    2020-03-16 17:21:02
    拉链法构造哈希表,插入value,哈希表自动计算相应的key,并将元素(key,value)插入,key冲突的元素通过链表挂在数组相应的key的位置。 #pragma once #include <iostream> using namespace std; const int ...
  • 哈希——拉链法

    千次阅读 2018-03-01 15:25:06
    首先写哈希——拉链法要知道哈希冲突。 哈希冲突: 对于两个数据元素的关键字 Ki 和 Kj (i != j),有 Ki != J ,但有: HashFun(Ki) == HashFun(Kj) 即不同关键字通过相同哈希哈数计算出相同的哈希地址,该种...
  • 九, 哈希表 9.1 哈希表的定义和特点 散列表(Hash table, 也叫哈希表),是根据关键码 - 值(Key - value)而直接进行访问的数据结构。...下图就是一个典型的哈希表(数组+链表实现的,使用拉链法解决冲突)
  • Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 实现...
  • 哈希表存储结构: 1.开放寻址法 2.拉链法 哈希表的主要作用: 把一个较大(0-10^9 )的数据映射到较小(0-N(N一般为10^5 到 10^6))的数据 哈希函数:可以把一个从-10^19 到10^19 的中的一个数映射到0-10^5之间的一个数 ...
  • JAVA哈希表的构建(拉链法

    千次阅读 2018-07-15 19:21:02
    哈希表是一个用途很广泛的数据结构,常用于需要进行大集合搜索的地方,比如腾讯QQ。对于上线的用户我们需要将其添加到一个集合中,以便对其进行各种处理。那么这个集合该采取哪种数据结构呢?最基本的数据结构就两种...
  • 也就是拉链特别长的时候,有什么好办法能够解决的吗?主要是为了解决查询的效率问题,我想过把拉链变为一棵红黑树,除了这个办法以外还有什么好办法吗?
  • 哈希表的开散列法(拉链法

    千次阅读 2018-03-01 21:56:28
    开散列:首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。 设元素的关键码为37, ...
  • 字典也叫散列表,最大的特点是通过key来查找其对应的值其时间复杂度是O(1),下面这篇文章就来给大家介绍介绍python利用拉链法实现字典的方法。 在Python中怎样用列表实现字典? 用列表实现字典最大的问题就是解决hash...
  • 哈希表拉链法

    千次阅读 2017-02-23 19:36:29
    数据结构实验:哈希表 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 在n个数中,找出出现次数最多那个数字,并且输出出现的次数。如果有多个结果,输出数字最小的那一个。 Input 单组数据,第...
  • 拉链法实现哈希表

    2018-01-04 17:01:00
    #include string.h> #include #include typedef struct node{ char *name;//字段名 char *desc;//描述 struct node *next;...#define HASHSIZE 100 //hash长度 static node* hashtable[HASHSIZE];//定
  • //整数哈希函数 } void insert(ListNode* hash_table[], ListNode* node, int table_len) { int hash_key = hash_func(node->val, table_len); node->next = hash_table[hash_key];//使用头插插入结点 hash_...
  • //将哈希表中的所有指针初始化为空 memset(htb->_tables, 0, sizeof(HashNode*)*htb->_len); } //销毁 void HTBDestory(HTB* htb) { assert(htb); //释放哈希表上每一条链上的节点 for (size_t i = 0; i ...
  • 哈希表查找 — 拉链法

    千次阅读 2015-07-26 17:33:06
    散列表(也叫哈希表),是根据关键字值而直接进行访问的数据结构。 本文采用除留余数法构造散列函数。 本文采用拉链法处理冲突。 根据原始数组建立一个哈希表哈希表为一个链表(一定要区分数组和链表),且要求哈希...
  • 哈希表拉链法解决冲突的时候怎么根据K进行查找值?假如k1,k2有冲突,现在查找k2的值?怎么查找。
  • 由于哈希表的查找高效性,在平时的算法中用的也是比较多。例如:字符串、单词个数的统计,只出现一次字符或者数字的统计,两个集合相同元素的查找等等,还有插入删除的高效(链地址)都可以用哈希表来解决。缺点...
  • 哈希表 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的...
  • #include <stdlib.h> #include <stdio.h> /* 一如既往的使用注释进行说明吧 建立哈希表 Hash_Table Node节点进行插入(值%n n=4) H(0)->Node->Node... 4 8 12 H(1)->Node->Node... ...
  • C++ 实现哈希表的实例

    2020-08-29 13:58:28
    主要介绍了C++ 实现哈希表的实例的相关资料,这里使用C++实现哈希表的实例帮助大家彻底理解哈希表的原理,需要的朋友可以参考下
  • 哈希表拉链法

    2021-01-11 19:37:44
    拉链法 Hash(KEY) = Positon; 在Postion下面形成一个单链表,存储所有以该Positon为存储地址的数据。 找一个比数据范围略大的大质数 例如数据范围是10W for(int i = 100000; ; i++) { bool bFlag = true; ...
  • Hash的实现——拉链法

    千次阅读 2018-11-21 13:04:22
    一.基础的概念问题 ...但是有时需要对大量数据进行查找以及插入删除操作,这时就需要用到哈希表,是根据关键码值(Key value)而直接进行访问的数据结构。 ·Hash我们百度一下英文意思就是把其弄乱,...
  • 例如:字符串、单词个数的统计,只出现一次字符或者数字的统计,两个集合相同元素的查找等等,还有插入删除的高效(链地址)都可以用哈希表来解决。所以这里对其做一个小小的总结。缺点可能是需要占用额外的内存...
  • 哈希表 拉链法

    2013-03-28 14:16:47
    哈希表: */ #include #include #include typedef struct node {  char data;  struct node *next; }link_list; int main() {  link_list *p,*p1,*q;  link_list a[10];  int b
  • C语言实现哈希表(链式

    千次阅读 多人点赞 2019-11-23 13:13:03
    笔者最近学习数据结构中的哈希表,并用C语言简单实现了。 当然源代码多有参考,此博客旨在交流心得 哈希表原理 结构体说明如下 源代码如下: #include<stdio.h> #include<stdlib.h> #define ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,789
精华内容 5,115
关键字:

哈希表拉链法