精华内容
下载资源
问答
  • HASH表原理

    2019-10-03 18:21:56
    HASH表原理大家都知道,在所有的线性数据结构...大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转...

    HASH表原理

    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

        具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

        不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。

    在java.util.HashMap中的关键代码:

       Entry[] table;
       static int hash(int h) {
            // This function ensures that hashCodes that differ only by
            // constant multiples at each bit position have a bounded
            // number of collisions (approximately 8 at default load factor).
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

        /**
         * Returns index for hash code h.
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
        final Entry<K,V> getEntry(Object key) {
            int hash = (key == null) ? 0 : hash(key.hashCode());
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }
        public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }

            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

        void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }

    转载于:https://www.cnblogs.com/creazy_windy/archive/2012/06/13/2548418.html

    展开全文
  • HASH表原理(装)

    2014-05-20 22:18:00
    HASH表原理大家都知道,在所有的线性数据...大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定 的算法函数既所谓的哈希函数转...

    HASH表原理

    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。

        具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定 的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组 空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到 数组的定位性能进行数据定位。

        不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转 换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就 会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一 并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。

    在java.util.HashMap中的关键代码:

       Entry[] table;
       static int hash(int h) {
            // This function ensures that hashCodes that differ only by
            // constant multiples at each bit position have a bounded
            // number of collisions (approximately 8 at default load factor).
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

        /**
         * Returns index for hash code h.
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }
        final Entry<K,V> getEntry(Object key) {
            int hash = (key == null) ? 0 : hash(key.hashCode());
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }
        public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }

            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

        void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            if (size++ >= threshold)
                resize(2 * table.length);
        }

     

    http://www.cnblogs.com/creazy_windy/archive/2012/06/13/2548418.html

    转载于:https://www.cnblogs.com/xiaxinggege/p/3740162.html

    展开全文
  • 一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。...大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间...

     

    一列键值对数据,存储在一个table中,如何通过数据的关键字快速查找相应值呢?不要告诉我一个个拿出来比较key啊,呵呵。 

    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 

    具体如何做呢?大家是否有注意到前面说的话:“数组可以通过下标直接定位到相应的空间”,对就是这句,哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

    不知道说到这里,一些不了解的朋友是否大概了解了哈希表的原理,其实就是通过空间换取时间的做法。到这里,可能有的朋友就会问,哈希函数对key进行转换,取余的值一定是唯一的吗?这个当然不能保证,主要是由于hashcode会对数组长度进行取余,因此其结果由于数组长度的限制必然会出现重复,所以就会有“冲突”这一问题,至于解决冲突的办法其实有很多种,比如重复散列的方式,大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。 

    Hash表这种数据结构在java中是原生的一个集合对象,在实际中用途极广,主要有这么几个特点:

    1.访问速度快

    2.大小不受限制

    3.按键进行索引,没有重复对象

    4.用字符串(id:string)检索对象(object)

    今天整理以前在学校写的一些算法,翻出来一个hash表的实现,就贴出来,自己也温习温习。
    先看看头文件,也就是数据结构的定义,相当于java中的接口的概念:

    #include <stdio.h>

    #define    HASHSIZE 256

    //定义hash表中的节点的类型
    struct    nlist{
        
    struct    nlist    *next;
        
    char    *name;
        
    char    *defn;
    };

    //定义接口中的函数,也就是对外来说,这个程序可以做什么
    unsigned    hash(
    char *s);//计算一个串的hash值
    struct    nlist    *lookup(char *s);//查找一个value,根据key
    struct    nlist    *install(char *name,char *defn);//插入一个key=value的对象


    然后是具体实现:

    #include <string.h>
    #include 
    "list.h"

    static struct nlist *hashtab[HASHSIZE];

    unsigned    hash(
    char *s) //取得hash值
    {
        unsigned    hashval;

        
    for(hashval = 0*!= '\0';s++)
                hashval 
    = *+ 31 * hashval;
        
    return hashval % HASHSIZE;
    }

    struct    nlist    *lookup(char *s)
    {
        
    struct    nlist    *np;

        
    for(np = hashtab[hash(s)]; np != NULL; np = np->next)
            
    if(strcmp(s,np->name) == 0)
                
    return np;
        
    return NULL;
    }

    struct    nlist    *install(char *name,char *defn)
    {
        
    struct    nlist    *np;
        unsigned    hashval;

        
    if((np = lookup(name)) == NULL){
            np 
    = (struct nlist *)malloc(sizeof(struct nlist));
            
    if(np == NULL || (np->name = strdup(name)) == NULL)
                    
    return NULL;
            hashval 
    = hash(name);
            np
    ->next= hashtab[hashval];
            hashtab[hashval] 
    = np;
        }
    else
            free((
    void *)np->defn);
        
    if((np->defn = strdup(defn)) == NULL)
                
    return NULL;
        
    return np;
    }

    很简单,只有两个外部接口,

    1. install(key, value),用来插入一个新的节点
    2. lookup(key),根据一个键来进行搜索,并返回节点

    代码很简单,主要用到的hash算法跟java中的String的hashcode()方法中用到的算法一样,使用:

     

    unsigned    hash(char *s)
    {
        unsigned    hashval;

        
    for(hashval = 0*!= '\0';s++)
                hashval 
    = *+ 31 * hashval;
        
    return hashval % HASHSIZE;
    }

     

    这里的31并非随意,乃是一个经验值,选取它的目的在于减少冲突,当然,hash冲突这个问题是不能根本避免的。这里只是一个人们在测试中发现的可以相对减少hash冲突的一个数字,可能以后会发现更好的数值来。

    转载于:https://www.cnblogs.com/mooner-hw/archive/2011/03/31/2000878.html

    展开全文
  • 父接口collection 子接口list 单列集合 有序,允许重复,允许存null ...arraylist底层是数组,可以通过下标直接定位到对应的元素所以查询更新的效率高,删除插入效率低,不保证线程安全 linkedlist底层是链表,

    父接口collection

    子接口list

    单列集合

    有序,允许重复,允许存null

    实现类arraylist

    单列集合

    有序,允许重复,允许存null

    底层数组,不安全

    实现类linkedlist

    单列集合

    有序,允许重复,允许存null

    底层链表(双向链表),不安全

    实现类vector

    底层数组,与arraylist的功能基本一样

    list常用实现类的区别

    arraylist底层是数组,可以通过下标直接定位到对应的元素所以查询更新的效率高,删除插入效率低,不保证线程安全

    linkedlist底层是链表,在内存中不是连续的空间,虽然有下标,但是还是需要遍历整个链表去找对应的元素,所以查询更新效率低,插入删除效率高

    vector:线程安全,效率低

    array和arraylist的区别

    array(数组)长度不可变,当数据超过容量大小时,会出现下标越界异常

    arraylist(集合)会自动扩容,一般是1.5倍

    子接口set

    单列集合

    没有定义有序无序,具体看实现类,不允许重复

    实现类hashset

    无序,不允许重复,允许存null

    底层是hashmap,哈希表结构,不安全

    实现类treeset

    自然顺序,不允许重复,不允许null

    底层是treemap,不安全

    hashset的子类linkedhashset

    是hashset的一个子类和hashset的方法一样,但是保证迭代顺序

    map

    双列集合,双列集合的根接口,键值对应,不能有重复键,但能有重复值

    子接口hashmap

    无序,不重复键,重复值,允许null值null键

    底层基于哈希表实现,不安全

    子接口treemap

    有序,不重复键,重复值,不允许null键,可以null值

    底层红黑树,不安全

    hashtable

    双列集合,不允许null键,null值,安全效率低

    concurrenthashmap

    线程安全效率高;比hashmap安全,比hashtable效率高

    hashtable和hashmap的区别

    1.hashtable同步,hashmap不同步
    2.hashmap允许null值null键,hashtable不允许

    展开全文
  • 大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 具体...
  • 查找(三)hash 与map

    2015-09-26 11:24:49
    一,hashtable原理: ...大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数
  • HASH 与MAP 的区别

    2017-02-17 13:09:53
    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 具体如
  • 一,hashtable原理: ...大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的...
  • hash表原理

    2011-03-29 21:03:06
    在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 ...
  • 一,hashtable原理: ...大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的...
  • Hash表原理

    千次阅读 2012-05-09 20:50:52
    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题
  • 哈希表又名散列表,其主要... 大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决...
  • hash 哈希表原理

    千次阅读 2008-08-25 23:29:00
    大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。 具
  • hash原理与一致性hash

    2013-05-21 22:36:00
    哈希表的原理与实现 一列键值对数据,存储在一个table中,如何... 大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是...
  • 哈希表简介

    2010-04-07 16:03:00
    哈希表又名散列表,其主要目的是用于解决数据的快速定位问题。... 大家都知道,在所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。而哈希表就是利用数
  • 剖析HashMap

    2020-10-21 13:24:30
    提起数组,相信大多数人都不陌生,那么数组到底是什么,数组的本质是一块连续的内存空间,存放着具有共同特性的内容,因为是一块连续的内存,我们就可以快速的定位,我们可以通过数组下标直接对其进行操作。数组的缺点让...
  • Sort a linked list in O(n log n) time using constant space complexity. [Thoughts]O(nlgn)的排序算法没几个,无非就是quick ...如果是数组,那么可以通过下标直接找到节点,但是对于链表,很明显没有下标这个东西
  • [Leetcode] Sort List

    2014-11-16 14:37:00
    Sort a linked list inO(nlogn) time using constant space complexity. Solution: O(nlgn)的排序算法没几个,无非就是quick sort, ...如果是数组,那么可以通过下标直接找到节点,但是对于链表,很明显没有下...
  • hash表

    2010-05-04 20:59:00
    Hash表理解 言归正传,哈希表又名散列表,其... (key-value这样的数据,要恰当的选择key,一般情况下key和value是等同的) 大家都知道,在所有的线性数据结构中,数组定位速度最快,因为它可通过数组下标直接...
  • 课程内容:首先了解下如何通过代码分析出CD和LV的偏移.通过逆向分析代码,我们找到了这个CD和LV的偏移,并且把判断的功能加入了智能吃药,经过不断的调试,我们成功的判断了物品的CD和LV,我们的智能加血更加完美了. 043 ...
  • 现代操作系统都使用分页... 虚拟地址如何通过页表转换为物理地址? 一、直接使用数组转换 最容易想到的映射方案是使用数组:每个数组元素保存一个物理地址,而把虚拟地址作为数组下标,这样就能够很容易地完成映射,
  • mongoDB内嵌文档查询

    千次阅读 2017-06-07 14:43:07
    查询集合中数组的其中一个元素: ... 在需要对数组中的值进行操作的时候,可通过位置或者定位操作符("$").(不要忽略这个点)数组是0开始的,可以直接下标作为键来选择元素。  基础数据如下: { "_id": ObjectId(

空空如也

空空如也

1 2 3
收藏数 52
精华内容 20
关键字:

数组如何通过下标直接定位