精华内容
下载资源
问答
  • hash表之拉链法处理冲突

    千次阅读 2014-08-16 17:01:07
    /*hash表之拉链法处理冲突:*/ 方法一: #define ARRLEN 17 #define NAMELEN 20 #define ADDRLEN 20 typedef struct _rec {  char name[NAMELEN];  char addr[ADDRLEN];  struct _rec *next; } rec; ...
    

    /*hash表之拉链法处理冲突:*/
    方法一:(不推荐)

    #define ARRLEN 17
    #define NAMELEN 20
    #define ADDRLEN 20

    typedef struct _rec
    {
        char name[NAMELEN];
        char addr[ADDRLEN];
        struct _rec *next;
    } rec;


    //hash函数,线性定址法和余数法结合。
    //得到的地址为数组的下标。
    //count为hash表长,即模。
    int hash(char *name, int count)
    {
        int hashcode = 0;
        int i;
        int len = strlen(name);

        for(i = 0; i < len; i++)
        {
            hashcode = hashcode * i + name[i];
        }

        return hashcode % count ;
    }


    /*
    添加一个记录,如果这个位置已有元素,则在该元素后拉链,添加到链中。
    数组中的每个元素的值为 结构体元素的指针。
    并且数组中的每个元素存储的指针域为带有头节点的链表的头节点。
    数组中的每个元素时不存储数据域的,因为头节点没有数据域。

    所以数组名为结构体元素的二级指针。
    */
    void hash_insert(rec **hashtable, int count, rec *record)
    {
        int hashcode = hash(record->name, count);
        rec *tmp;


    //hash地址没有被占用,直接填充。
        if(hashtable[hashcode] == NULL)
        {
            if( (hashtable[hashcode] = (rec *)malloc(sizeof(rec))) == NULL)
            {
                fprintf(stderr, "malloc error\n");
            }
            else
            {
                strcpy(hashtable[hashcode]->name, record->name);
                strcpy(hashtable[hashcode]->addr, record->addr);
                hashtable[hashcode]->next = NULL;
            }
        }
        else
        {//被占用了,则填充在后面的链的结尾处。
            tmp = hashtable[hashcode];

            while(tmp->next != NULL)
            {
                tmp = tmp->next;
            }//定位到链尾。
           
            if( (tmp->next = (rec *)malloc(sizeof(rec))) == NULL)
                fprintf(stderr, "malloc error\n");
            else
            {
                strcpy(tmp->next->name, record->name);
                strcpy(tmp->next->addr, record->addr);
                tmp->next->next = NULL;
            }
        }
    }

    /*
    hash_search:
    */
    int hash_search(rec **hashtable, int count, rec *record)
    {
        int hashcode = hash(record->name, count);
        rec *tmp = hashtable[hashcode];

        while(tmp != NULL)
        {
            if(strcmp(tmp->name, record->name) == 0)
            {
                strcpy(record->addr, tmp->addr);
                return hashcode;
            }
            //else tmp=temp->next;
        }

        return -1;
    }

    /*
    删除某个记录,
    */
    void hash_delete(rec **hashtable, int count, char *name)
    {
        int hashcode = hash(name, count);
           
        rec *tmp1, *tmp2;

        //没有该记录。
        if(hashtable[hashcode] == NULL)
            return;

            //在第一个位置就找到记录。
        else if(hashtable[hashcode] != NULL &&
            strcmp(hashtable[hashcode]->name, name) == 0)
        {
            free(hashtable[hashcode]);
            hashtable[hashcode] = NULL;
        }
        else
        {
            tmp1 = hashtable[hashcode];

            while(tmp1->next != NULL && strcmp(tmp1->next->name, name) != 0)
                tmp1 = tmp1->next;

            if(tmp1->next != NULL)
            {
                tmp2 = tmp1->next;
                tmp1->next = tmp2->next;
                free(tmp2);
            }
        }
    }

       
    int menu_select(void)
    {
        char s[80];
        int c;

        do
        {
            printf("1. Enter a record\n");
            printf("2. Search a record\n");
            printf("3. Delete a record\n");
            printf("4. Quit\n");
            printf("Enter a choice:\n");

            fgets(s, 80, stdin);
            c = atoi(s);
        } while(c < 1 || c > 5);

        return c;
    }


    void rec_insert(rec **hashtable, int count)
    {
        rec tmp;
        int len;

        printf("Enter the name:\n");
        fgets(tmp.name, NAMELEN, stdin);
        printf("Enter the addr:\n");
        fgets(tmp.addr, ADDRLEN, stdin);

        len = strlen(tmp.name);
        if(tmp.name[len -1] == '\n')
            tmp.name[len - 1] = '\0';
       
        len = strlen(tmp.addr);
        if(tmp.addr[len -1] == '\n')
            tmp.addr[len -1] = '\0';

        tmp.next = NULL;

        hash_insert(hashtable, count, &tmp);
    }


    void rec_search(rec **hashtable, int count)
    {
        rec tmp;
        int len;

        int loc;

        printf("Enter the name:\n");
        fgets(tmp.name, NAMELEN, stdin);
       
        len = strlen(tmp.name);
        if(tmp.name[len -1] == '\n')
            tmp.name[len -1] = '\0';

        if( (loc = hash_search(hashtable, count, &tmp)) != -1)
        {
            printf("%s\n%s\n", tmp.name, tmp.addr);
        }
        else
            printf("can not found\n");
    }

    void rec_delete(rec **hashtable, int count)
    {
        char s[NAMELEN];
        int len;

        printf("Enter the name:\n");
        fgets(s, NAMELEN, stdin);
        len = strlen(s);
        if(s[len -1] == '\n')
            s[len -1] = '\0';
       
        hash_delete(hashtable, count, s);
    }


    int main(void)
    {
        rec *a[ARRLEN];
        int choice;

        memset(a, 0, sizeof(a));

        while(1)
        {
            choice = menu_select();
            switch(choice)
            {
            case 1:
                rec_insert(a, ARRLEN);
                break;
            case 2:
                rec_search(a, ARRLEN);
                break;
            case 3:
                rec_delete(a, ARRLEN);
                break;
            case 4:
                exit(0);
            }
        }
    }

    ----------------------------

    (二)步骤:

    (1)构建一个链表的节点的结构体ListNode;包含两个字段一个字段是 关键字,一个是next;

    那么使用ListNode*类型的变量,就可以保存一个带有头节点的链表了。

    (2)构建一个HashTable的结构体;包含两个字段,一个是hashTable的大小,size,还有一个是

    ListNode*的数组 ListNode**  lists,即 lists[i] 就是 hash值为i的链表,i为通过hash函数得到的 hash地址 。

    (注意:HashTable数组中的每个元素存储的是链表的 头指针,并没有包含关键字的值, 关键字都是存储在链表的头指针后面的节点中 )

    (3)构造hash函数,如 int Hash(KeyType key, int prime);

    取余法,得到地址,返回。

    (4)初始化HashTable,数组中每个元素为链表的头结点。


    (5)int hashSearch(HashTable h , KeyType key);

    可有key,根据hash函数,得到key所指的链表的头指针,然后依次遍历该链表,看是否可以查到。

    (6) hashInsert(HashTabel  h ,KeyType key)

    首先调用hashSearch函数,如果,没有查找到,则插入。



    ---------------------------


    方法二:(推荐)

    /*
    *哈希表 拉链法
    */
    #include<stdio.h>
    #include<stdlib.h>


    #define MinTableSize 10

    typedef int ElemType;
    typedef unsigned int Index;

    typedef struct ListNode
    {
     ElemType element;
     struct ListNode *next;
    }*Position;

    typedef Position List;


    /*
    类型说明:
    ListNode类型:
    List=Position=ListNode*;
    HashTbl*=HashTable;
    List* TheLists,所以TheList是ListNode**类型的;
    */

    typedef struct HashTbl
    {
     int TableSize;
      List *TheLists;
    }*HashTable;

    /*因为表长通常都是prime*/
    //这个写的好像不对。
    int NextPrime(int N)
    {
     int i;

     if(N%2==0)
      N++;
     for(;;N+=2)
     {
      for(i=3;i*i<=N;i+=2)
       if(N%i==0)
        return 0;
      return N; 
     }
    }

    /*hash函数*/
    Index Hash(ElemType Key,int TableSize)
    {
     return Key%TableSize;
    }

    /*
    初始化hash表。
    hash表的数组名是ListNode**;
    表中的每个元素为listNode*;
    初始化时每个元素都是一个空链,所以每个元素的next为null;
    */
    HashTable InitializeTable(int TableSize)
    {
     HashTable H;
     int i;

     if(TableSize<MinTableSize)
     {
      printf("Table size too small!\n");
      return NULL;
     }
     
     /*Allocate table*/
     H=(HashTable)malloc(sizeof(struct HashTbl));
     if(NULL==H)
       printf("Out of space!!!\n");

     H->TableSize=NextPrime(TableSize);
     
     
     H->TheLists=(List *)malloc(sizeof(List)*H->TableSize);
     if(NULL==H->TheLists)
     {
       printf("Out of space!!!\n");
       free(H);
       return NULL;
     }
     
     for(i=0;i<H->TableSize;i++)
     {
      H->TheLists[i]=(Position)malloc(sizeof(struct ListNode));
      if(NULL==H->TheLists[i])
       printf("Out of space!!!\n");
      else
       H->TheLists[i]->next=NULL;

      H->TheLists[i]->element=0;//哈希表中所有元素的key初始化为0
     }

     return H;
    }

    /*hash查找*/
    Position Find(ElemType Key,HashTable H)
    {
     Position p;
     List L;

     L=H->TheLists[Hash(Key,H->TableSize)];
     p=L->next;
     while(p!=NULL&&p->element!=Key)
      p=p->next;

     return p;
    }

    /*
    hash插入
    hashTable中的每个元素存储的是带有头节点的链表的头节点。
    头节点的数据域是没有数据的。
    所以如果一个存储一个数据,数据存储的是在hashTable元素的next节点中。
    */
    void Insert(ElemType Key,HashTable H)
    {
     Position pos,newCell;
     List L;

     pos=Find(Key,H);
     if(NULL==pos)/*没有找到关键字key*/
     {
      newCell=(Position)malloc(sizeof(struct ListNode));
      if(NULL==newCell)
        printf("Out of space!!!"); 
      else
      {
       L=H->TheLists[Hash(Key,H->TableSize)];
       newCell->next=L->next;
       newCell->element=Key;/*头插法*/
       L->next=newCell;
      }
     }
    }

    /*
    删除hash表。
    */
    void DestroyTable(HashTable H)
    {
     int i;

     for(i=0;i<H->TableSize;i++)
     {
      Position p=H->TheLists[i];
      Position temp;

      while(p!=NULL)
      {
       temp=p->next;
       free(p);
       p=temp;
      }
     }
     free(H->TheLists);
     free(H);
    }

    void printHash(HashTable H,int len)
    {
     int i;
     for(i=0;i<len;i++)
     {
      Position p=H->TheLists[i];
      while(p)
      {
       printf("address=%d value=%d\n",i,p->element);
       p=p->next;
      } 
     }

    }
    int main()
    {
     
     HashTable H;
     Position p=NULL;
     int array[]={19,14,23,01,68,20,84,27,55,11,10,79};
     int len=sizeof(array)/sizeof(array[0]);
     int i;
     ElemType k;
             
     H=InitializeTable(len);
     for(i=0;i<len;i++)
     {
      Insert(array[i],H); 
     }
     printHash(H,len);
     printf("\n\n");
     
     printf("please input the value which need find:");
     scanf("%d",&k);
     p=Find(k,H);
     if(p)
       printf("%d",p->element);
     else
       printf("cannot find the value!");
     printf("\n\n");
     
     printf("free the table\n");
     DestroyTable(H);
     printf("it's done!!!");
     printf("\n\n");

     return 0;
    }



    展开全文
  • 散列表线性探测法外拉链法 #include &amp;amp;lt;iostream&amp;amp;gt; #include &amp;amp;lt;algorithm&amp;amp;gt; using namespace std; struct Node { int key; Node *next; }; Node ...

    散列表线性探测法外拉链法
    这里写图片描述

    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct Node
    {
        int key;
        Node *next;
    };
    Node HashTable[13];
    int a[13];
    int InsertHT(int x,int w)
    {
        int adr;
        Node *p;
        adr=x%w;
        p=&HashTable[adr];
        while(p->next)
        {
            if(p->next->key==x)
            return -1;
            p=p->next;
        }
        Node *s;
        s=new Node;
        s->key=x;
        s->next=p->next;
        p->next=s;
        return 1;
    }
    void CreateHT(int n,int m,int p)
    {
        for(int i=0;i<n;i++)
        {
            HashTable[i].key=i;
            HashTable[i].next=NULL;
        }
        for(int i=0;i<m;i++)
            InsertHT(a[i],p);
    }
    void Display(int n,int m)
    {
       int add[13],j,count;
       Node *q;
       for(int i=0;i<13;i++)
       {
           j=0;count=0;
           q=(&HashTable[i])->next;
           while(q!=NULL)
           {
               add[j]=q->key;
               j++;
               count++;
               q=q->next;
           }
           sort(add,add+count);
           q=(&HashTable[i])->next;
           j=0;
           while(q!=NULL)
           {
               q->key=add[j];
               j++;
               q=q->next;
           }
       }
       cout<<"  "<<0<<endl;
       for(int i=1;i<13;i++)
       {
           q=&HashTable[i];
           cout<<"  ";
           while(q->next!=NULL)
           {
               cout<<q->key<<" ";
               q=q->next;
           }
           cout<<q->key<<endl;
       }
    }
    int main()
    {
        for(int i=0;i<13;i++)
        cin>>a[i];
        CreateHT(13,13,13);
        Display(13,13);
        return 0;
    }
    
    
    
    
    展开全文
  • class StorePageMap {  /**  * The table, resized as necessary. Length MUST Always be a power of two.  */  private Entry[] table;  /** ... * The number of key-value mappi
    class StorePageMap {
    



        /**
         * The table, resized as necessary. Length MUST Always be a power of two.
         */
        private Entry[] table;

        /**
         * The number of key-value mappings contained in this identity hash map.
         */
        private int size;
     
        /**
         * The next size value at which to resize (capacity * load factor).
         * @serial
         */
        private int threshold;
     




        /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        StorePageMap() {
            threshold = 12;
            table = new Entry[17];
        }





     
        /**
         * Returns the number of key-value mappings in this map.
         *
         * @return the number of key-value mappings in this map.
         */
        final int size() {
            return size;
        }
     
        /**
         * Returns <tt>true</tt> if this map contains no key-value mappings.
         *
         * @return <tt>true</tt> if this map contains no key-value mappings.
         */
        final boolean isEmpty() {
            return size == 0;
        }

        /**
         * Returns the first StorePage for the given key.
         */
        final TableStorePage get(long key) {
            int i = (int)(key % table.length);
            Entry e = table[i];
            while (true) {
                if (e == null)
                    return null;
                if (e.key == key)
                    return e.value;
                e = e.next;
            }
        }

        /**
         * Returns <tt>true</tt> if this map contains a StorePage for the
         * specified key.
         *
         */
        final boolean containsKey(long key) {
            return (get(key) != null);
        }

     
        /**
         * Add the StorePage with the key. Multiple StorePage for the same key are valid.
         * The cause are multiple changes in one transaction. With SavePoints a rollback to a older
         * StorePage is valid.<p>
         * The latest StorePage is placed at first pos.
         */
        final TableStorePage add(long key, TableStorePage value) {
            int i = (int)(key % table.length);

            table[i] = new Entry(key, value, table[i]);
            if (size++ >= threshold)
                resize(2 * table.length);
            return null;
        }


        /**
         * Rehashes the contents of this map into a new array with a
         * larger capacity.  This method is called automatically when the
         * number of keys in this map reaches its threshold.
         *
         * If current capacity is MAXIMUM_CAPACITY, this method does not
         * resize the map, but but sets threshold to Integer.MAX_VALUE.
         * This has the effect of preventing future calls.
         *
         * @param newCapacity the new capacity, MUST be a power of two;
         *        must be greater than current capacity unless current
         *        capacity is MAXIMUM_CAPACITY (in which case value
         *        is irrelevant).
         */
        final private void resize(int newCapacity) {

            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable);
            table = newTable;
            threshold = (int)(newCapacity * 0.75f);
        }

        /**
         * Transfer all entries from current table to newTable.
         */
        final private void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) {
                Entry e = src[j];
                if (e != null) {
                    src[j] = null;
                    do {
                        Entry next = e.next;
                        e.next = null;
                        int i = (int)(e.key % newCapacity);
                        //The order for StorePages with the same key must not change
                        //that we need to find the end of the link list. This is different to a typical HashTable
                        if(newTable[i] == null){
                            newTable[i] = e;
                        }else{
                            Entry entry = newTable[i];
                            while(entry.next != null) entry = entry.next;
                            entry.next = e;
                        }
                        e = next;
                    } while (e != null);
                }
            }
        }

     
        /**
         * Removes the mapping for this key from this map if present.
         *
         * @param  key key whose mapping is to be removed from the map.
         * @return previous value associated with specified key, or <tt>null</tt>
         *           if there was no mapping for key.  A <tt>null</tt> return can
         *           also indicate that the map previously associated <tt>null</tt>
         *           with the specified key.
         */
        final TableStorePage remove(long key) {
            int i = (int)(key % table.length);
            Entry prev = table[i];
            Entry e = prev;

            while (e != null) {
                Entry next = e.next;
                if (e.key == key) {
                    size--;
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    return e.value;
                }
                prev = e;
                e = next;
            }
            return null;
        }


        /**
         * Removes all mappings from this map.
         */
        final void clear() {
            Entry tab[] = table;
            for (int i = 0; i < tab.length; i++)
                tab[i] = null;
            size = 0;
        }

        /**
         * Returns <tt>true</tt> if this map maps one or more keys to the
         * specified value.
         *
         * @param value value whose presence in this map is to be tested.
         * @return <tt>true</tt> if this map maps one or more keys to the
         *         specified value.
         */
        final boolean containsValue(TableStorePage value) {
            Entry tab[] = table;
                for (int i = 0; i < tab.length ; i++)
                    for (Entry e = tab[i] ; e != null ; e = e.next)
                        if (value.equals(e.value))
                            return true;
            return false;
        }



        static class Entry{
            final long key;
            final TableStorePage value;
            Entry next;

            /**
             * Create new entry.
             */
            Entry(long k, TableStorePage v, Entry n) {
                value = v;
                next = n;
                key = k;
            }

        
        }


    }

    展开全文
  • 对于给定的一组整数和散列函数,分别采用线性探测法和拉链法处理冲突构造散列表,并在这两种方法构建的散列表中查找整数K,比较两种方法的时间和空间性能。
  • 拉链法处理哈西冲突

    千次阅读 2016-11-07 13:58:59
    上一篇博客介绍了哈希表及处理哈西冲突的一种算法——开放定址法,这篇博客在介绍一下处理哈西冲突的另一种方法——拉链法。就是建立哈希表后,在每个位置下联一条链表,将数据用哈希函数处理后放入相应的链表中。 ...

            上一篇博客介绍了哈希表及处理哈西冲突的一种算法——开放定址法,这篇博客在介绍一下处理哈西冲突的另一种方法——拉链法。就是建立哈希表后,在每个位置下联一条链表,将数据用哈希函数处理后放入相应的链表中。

            我个人认为就处理哈希冲突的这两种算法来说各有利弊,因为建立哈希表为了便于查找;使用开放定址法时,当第一次定位没找到时,会向后遍历直到找到或遍历完整个哈希表为止,极端时要遍历整个表。而拉链法在定位后,只用向当前位置下的链表遍历进行查找,但如果链表过长是也会降低效率;我们可以使哈希表足够长以减少链表的长度,提高效率。


    #include<iostream>
    #include<vector>
    using namespace std;
    template<class K,class V>

    struct HashNode                                   //哈希表节点,保存数据
    {
     K _key;
     V _value;
     HashNode<K,V>* next;
      HashNode(const K& key,const V& value)
       :_key(key)
       ,_value(value)
       ,next(NULL)
      {}
    };


    template<class K,class V>
    class HashTable
    {
     typedef HashNode<K,V> Node;

    public:

     HashTable()
      :_size(0)
     {}

     ~HashTable()
     {
         for(size_t i=0;i<_table.size();i++)
      {
       Node* cur=_table[i];
       if(cur==NULL)
        continue;
       else
       {
        while(cur)
        {
         Node* prev=cur;
         cur=cur->next;
         delete prev;
         prev=NULL;
        }
       }
      }
      _size=0;
          _table.clear();
     }

     bool Insert(const K& key,const V& value)                      //插入数据
     {

       CheckSize();
      size_t index=_HashFunc(key,_table.size());
      Node* ret=new Node(key,value);
      if(Find(key))
       return false;
      
       ret->next=_table[index];
       _table[index]=ret;
       _size++;
       return true;
     }

     Node* Find(const K& key)                              //查找
     {
      if(_table.size()==0)
       return NULL;
      size_t index=_HashFunc(key,_table.size());
      Node* cur=_table[index];
      while(cur)
      {
       if(cur->_key==key)
        return cur;

       cur=cur->next;
      }
      return NULL;
     }

     bool Remove(const K& key)                                    //删除
     {
      if(_table.size()==0)
       return false;
      size_t index=_HashFunc(key,_table.size());
      Node* prev=NULL;
      Node* cur=_table[index];
      while(cur)
      {
       if(cur->_key==key)
       {
        if(prev==NULL)
         _table[index]=cur->next;
        else
         prev->next=cur->next;
        delete cur;
        _size--;
        return true;

       }
       prev=cur;
       cur=cur->next;

      }
      return false;
     }


     void Display()                                             //打印
     {
      if(_table.size()==0)
       return;
      for(size_t i=0;i<_table.size();i++)
      {
       printf("table[%d]->",i);
       Node* cur=_table[i];
       while(cur)
       {
        cout<<cur->_key<<"->";
         cur=cur->next;

       }
       cout<<"NULL"<<endl;
      }
     }


    protected:

     size_t _HashFunc(const K& key,size_t size)                     //哈希函数
     {
      return key%size;
     }


     void CheckSize()                                                               //检查容量并增容
     {
      if(_size==0||_size==_table.size())
      {
       vector<Node*> temp;
       temp.resize((GetNextPrime(_table.size())));
       for(size_t i=0;i<_table.size();i++)
       {
       Node* cur=_table[i];
         while(cur)
         {
          Node* next=cur->next;
          size_t index=_HashFunc(cur->_key,temp.size());
          cur->next=temp[index];
          temp[index]=cur;
          cur=next;

         }
       }
       temp.swap(_table);
      }
     }


     size_t GetNextPrime(size_t num)                                                      //增容素数数列,降低哈西冲突
     {
      long long PrimeSize[28]={53,97,193,389,769,1543,3079,
       6151,12289,24593,49157,98317,196613,393241,786433ul,
       1572869ul,3145739,6291469,12582917,25165843,50331653,
       100663319,201326611,402653189,805306457,1610612741,
       3221225473,4294967291};

      for(size_t i=0;i<28;i++)
      {
       if(PrimeSize[i]>num)
       {
        return PrimeSize[i];
       }
       else
        continue;
      }

      return 4294967291;

     }

     void Swap(HashTable<K,V>& hs)
     {
      _table.swap(hs._table);
      swap(_size,hs._size);
     }
    private:
     vector<Node*> _table;
     size_t _size;

    };

    #include"HashLink.h"
    #include<cstdlib>
    using namespace std;
    int main()
    {
     int a[10]={12,10,2,52,0,43,65,76,23,57};
     HashTable<int,int> hash;
     for(int i=0;i<10;i++)
     {
      hash.Insert(a[i],i);
     }
     hash.Remove(52);
     hash.Remove(34);
     hash.Remove(12);

     hash.Display();
     system("pause");
     return 0;
    }



    展开全文
  • 因为hashMap对于冲突处理采用的是拉链法,所以对拉链法进行详解。其他后续再说。 一、哈希?散列表,根据key值快速访问value 二、哈希冲突解决 1、开放定址法 a、线性探查法 b、线性补偿探查法 c、随机探测 2、...
  • hash表拉链法解决冲突

    千次阅读 2017-03-07 18:34:03
    散列表(Hash table) 也称为 哈希表 。是字典的一种抽象。比如说你要查一个字,通过这个字的拼音首字母,找到...如果两个不同的 key`算出了同一个索引,此时就要用到一定的方法来解决哈希冲突。 哈希函数 哈希函数
  • //哈希表(拉链法) #include<iostream> #include<cstring> using namespace std; const int N=100003; int h[N],e[N],ne[N],idx; void insert(int x) { //拉链法 int k=(x%N+N)%N; e[idx]=x; ne[idx]...
  • hash表的拉链法解决冲突

    千次阅读 2014-05-30 15:15:25
    //拉链法对hash table的溢出处理 #include #include #include #define MAX_CHAR 10 #define TABLE_SIZE 13 typedef struct element { char key[MAX_CHAR]; //other fields }element ; typedef struct List { ...
  • 哈希表 拉链法解决冲突原理:(大数对应一个小数,加快查找速率)建立一条拉链,每个拉链为一个槽,每个槽涵盖一个链表,将所有处理过的数放入对应槽的链表中 #include<iostream> #include<cstring> ...
  • 一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。 一、拉链法 ...
  • 哈希冲突拉链法

    千次阅读 2015-09-10 19:56:17
    解决哈希冲突一种比较直接的办法就是,将大小为M的数组的每一个元素指向一条链表,链表中的每一个节点都存储一个哈希值为该索引的键,这就是拉链法。 该方法的基本思想就是选择足够大的M,使得所有的链表都尽可能短...
  • 哈希冲突详解、拉链法、开地址法

    万次阅读 2015-10-29 23:33:12
    哈希冲突详解 我喜欢用问答的形式来学习,这样可以明确许多不明朗的问题。 什么是哈希冲突?比如我们要去买房子,本来已经看好的房子却被商家告知那间房子已经被其他客户买走了。... 方法2:开地址法何为拉链法
  • 数据结构——拉链法(链地址法)

    千次阅读 2019-12-10 20:54:16
    当存储结构是链表时,多采用拉链法,用拉链法处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0..m-1]存放各个链表的头...
  • 哈希冲突详解 我喜欢用问答的形式来学习,这样可以明确许多不明朗的问题。   什么是哈希冲突?   比如我们要去买房子,本来已经看好的房子却被商家告知那间房子已经被其他客户买走了。这就是生活中实实...
  • 基于拉链法实现的map,解决了地址冲突的问题。
  • 本文探讨拉链表解决哈希冲突的方式和几种常见的散列函数。  首先,什么是散列表?  对于一个数组,我们在O(1)时间复杂度完成可以完成其索引的查找,现在我们想要存储一个key value的键值对,我们可以根据key生成...
  • 哈希表查找 — 拉链法

    千次阅读 2015-07-26 17:33:06
    本文采用拉链法处理冲突。 根据原始数组建立一个哈希表,哈希表为一个链表(一定要区分数组和链表),且要求哈希表有固定大小。该方法将所有冲突的记录存储在一个链表中,并将这些链表的表头指针放在数组中。衡量一...
  • 拉链法和线性探测法解决哈希冲突 转自:http://www.tuicool.com/articles/QNjAbaf   前言 前面学习到的几种算法比如 红黑树 , 二叉搜索树 ,查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一...
  • //使用头插插入结点 hash_table[hash_key] = node; } bool search(ListNode* hash_table[], int value, int table_len) { int hash_key = hash_func(value, table_len); ListNode* head = hash_table[hash_key...
  • ;1.顺序栈实例演示;1.顺序栈实例演示;1.顺序栈实例演示;1.顺序栈实例演示;
  • (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况; (3)开放定址法为减少冲突...
  • 拉链法(链地址法)

    万次阅读 多人点赞 2016-03-24 10:25:53
    当存储结构是链表时,多采用拉链法,用拉链法处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。有m个散列地址就有m个链表,同时用指针数组T[0..m-1]存放各个链表的头...
  • 哈希冲突详解 我喜欢用问答的形式来学习,这样可以明确许多不明朗的问题。 什么是哈希冲突? ...比如我们要去买房子,本来已经看好的房子却被商家告知那间房子已经被其他客户买走了。... 方法1:拉链法 方法2:...
  • 在工业界,主要用拉链法来解决哈希冲突,称之为哈希桶的概念。请实现一个简单的哈希表,将如下信息,插入到哈希表中。 哈希表的哈希桶数量设置为10,以员工编号为input来计算哈希后的key,哈希函数使用取余法,编码...
  • /* ... * All rights reserved. * 文件名称:项目3.cbp ...相比线性探查,拉链法适用于大数据,它是把所有的同义词用单链表链接起来,利用哈希函数求出每个关键字的地址,同一地址的利用链表存放在一起。
  • 例如:字符串、单词个数的统计,只出现一次字符或者数字的统计,两个集合相同元素的查找等等,还有插入删除的高效(链地址)都可以用哈希表来解决。所以这里对其做一个小小的总结。缺点可能是需要占用额外的内存...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,963
精华内容 3,585
关键字:

拉链法处理冲突