`
alex1960
  • 浏览: 63720 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

Hashtable 的实现原理

    博客分类:
  • JAVA
阅读更多
1 基本原理

  我们使用一个下标范围比较大的数组,它通过一个结构体Entry来表示哈希表中的单个元素,这个结构体中有四个成员:
(1)key :表示键,即哈希表中的关键字。
(2)val :表示值,即跟关键字所对应值。
(3)Entry<K,V> next :指向下一个Entry,(主要用来解决冲突)
(4)hash :它是一个int类型,用于表示键所对应的哈希码来存储元素
数组的Entry的存放位置index是根据 h & (length-1) 其中h为key的hash值,lenth为数组的大小,也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。数组初始大小为8,当元素大于或等于数组的threshold就重新new一个length为当前数组两倍的新数组,旧的数组里的数据需要转换的新的数组:
void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
               
            }
        }
    }
但是,index不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

2.解决冲突
void addEntry(int hash, K key, V value, int index) {
Entry<K,V> e = table[index];
        table[index] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
        }
}
3.获取数据
public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = 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.equals(k)))
                return e.value;
        }
        return null;
    }
分享到:
评论

相关推荐

    HashMap和HashTable底层原理以及常见面试题

    HashMap和HashTable底层原理以及常见面试题 HashMap和HashTable是Java中两个常用的数据结构,都是基于哈希表实现的,但它们之间存在着一些关键的区别。本文将深入探讨HashMap和HashTable的底层原理,并总结常见的...

    hashtable购物车Session+Hashtable实现

    #### 三、购物车实现原理 ##### 1. 需求分析 在设计购物车时,需要考虑的核心数据有: - 商品ID - 商品数量 其他商品信息(如名称、价格等)通常已经存储在数据库中,因此只需通过商品ID从数据库中检索即可。 ####...

    java软件技术文档-深入java8的集合5:Hashtable的实现原理.pdf

    【Java软件技术文档-深入Java8的集合5:Hashtable的实现原理】 在Java编程语言中,集合框架是不可或缺的一部分,而Hashtable是其中一种古老的、线程安全的哈希表实现。尽管现在更多地使用HashMap或...

    HashTable

    本文将深入探讨基于C语言实现的HashTable,解析其源码,揭示其工作原理和优化策略。 一、哈希表的基本概念 1. 哈希函数:哈希表的核心是哈希函数,它将键转化为数组索引,使得键值可以快速定位。一个好的哈希函数...

    WinFormHashTable最简单用法,.net hashtable ,hashtable ,hashtable用法

    哈希表(Hashtable)是.NET框架中的一种常用数据结构,主要用作键值对存储,它提供了快速的数据存取方式。在WinForm应用程序中,我们可能会利用...理解其工作原理和使用技巧对于.NET开发人员来说是非常重要的。

    简单HashTable c实现

    这个简单的哈希表实现虽然基础,但已经具备了核心功能,适合学习和理解哈希表的工作原理。为了进一步提高性能,可以考虑动态调整哈希表大小、使用更高效的冲突解决策略(如双重哈希)或者优化哈希函数以减少冲突。...

    HashMap底层实现原理HashMap与HashTable区别HashMap与HashSet区别.docx

    HashMap的核心原理是通过散列函数将键对象转换为哈希码,然后使用这个哈希码来确定键值对在内部数组中的位置。哈希函数的设计使得相同的键会产生相同的哈希码,从而保证键值对的存储位置一致。然而,由于哈希表的...

    阿里巴巴 面经

    HashTable实现原理** - 类似于HashMap,但所有方法都是同步的,保证了线程安全性。 - 不允许键或值为null。 **15. HashMap与HashTable的区别** - **线程安全**:`HashTable`的所有方法都是同步的,而`HashMap`...

    hashtable存储数据.rar

    此外,`Hashtable`实现了`Map`接口,所以也可以使用`entrySet()`方法获取所有键值对的`Set`视图,方便进行遍历和操作。 在实际开发中,由于`Hashtable`的线程安全特性,它通常在需要跨线程共享数据时使用。但是,`...

    hashmap与hashtable区别

    历史背景及实现原理 - **Hashtable**:该类继承自`Dictionary`类,并且实现了`Map`接口。它最早出现在Java 1.0版本中,可以视为早期实现键值对存储的一种方式。 - **HashMap**:相比之下,`HashMap`是在Java 1.2...

    c#重写HashTable

    在C#编程中,`HashTable`...以上就是关于在C#中重写`HashTable`的相关知识点,包括理解`HashTable`的原理、重写的原因、步骤、注意事项以及泛型替代方案。通过这些知识,开发者可以更好地理解和定制自己的散列表实现。

    经典讲解List和ArrayList和Vector和HashTable和HashMap区别

    - **存储方式**:`List`接口的实现(如`ArrayList`和`Vector`)是有序的,而`Map`接口的实现(如`HashTable`和`HashMap`)是键值对形式,通过键来查找值。 - **数据访问**:`ArrayList`和`Vector`支持通过索引访问...

    12 HashTable.rar

    严蔚敏教授的教材中详细讲解了这些概念,并提供了具体的算法实现,帮助读者理解并掌握哈希表的工作原理和应用。通过学习这部分内容,开发者可以更好地利用哈希表解决实际问题,提升程序的效率。

    Hashtable简述

    这种数据结构利用哈希表的原理,通过key的哈希码实现快速查找,大大提高了数据检索的效率。由于键和值都是object类型,因此可以存储任何类型的对象。 **一、哈希表的基础** 哈希表(Hashtable)的核心特性在于它的...

    hashtable和dictionary的探讨

    而字典(Dictionary)是.NET Framework 2.0之后引入的数据结构,它也实现了哈希表的概念,但在某些方面有所改进。Dictionary同样提供O(1)的平均查找时间,但它是非线程安全的,这使得它在单线程环境中具有更高的性能...

    C语言hashtable

    标题中的"C语言hashtable"指的是使用C语言编写的哈希表实现。在C/C++中,我们通常需要自己设计哈希表的结构并实现相关的哈希函数、冲突解决策略以及插入、删除、查找等操作。这个描述暗示了提供的.c文件包含了一个...

    HashTable Sort

    #### 二、HashTable Sort 的工作原理 1. **创建 HashTable**:创建一个 HashTable 对象,并定义它的初始容量和装载因子(Load Factor)。装载因子是指 HashTable 占用的空间比例,一般设置为 0.75 左右。 ```...

    php中hashtable实现示例分享

    需要强调的是,尽管我们可以从源码中了解HashTable的实现原理,但绝大多数情况下,开发者无需直接操作HashTable的底层细节。因为PHP提供的数组操作接口已经足够完善和方便,使得开发者可以更加专注于业务逻辑的实现...

Global site tag (gtag.js) - Google Analytics