`
利li香
  • 浏览: 37294 次
  • 性别: Icon_minigender_2
社区版块
存档分类
最新评论

我对Hashtable的理解

阅读更多

一、哈希表的定义:

哈希表也叫散列表,是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

        二、哈希表的优势:

          数据结构中,有个时间算法复杂度O(n)的概念来衡量某种算法在时间效率上的优劣。哈希表的理想算法复杂度为O(1),也就是说利用哈希表查找某个值,系统所使用的时间在理想情况下为定值,这就是它的优势。那么哈希表是如何做到这一点的呢?

  三、哈希表是如何发挥优势的:

      我们定义一个很大的有序数组,想要得到位于该数组第n个位置的值,它的算法复杂度为O(1)。哈希表利用哈希函数将需要存储的内容的关键值转换为这个有序数组中的某个值,在被存储内容和有序数组之间建立了映射关系。这样,下次我们对这个值进行查找时只要使用同一个哈希函数对关键值进行转换,找到这个数组值就可以了。

      四、举例加深理解

    如果还没有明白是怎么回事的话,那我们来举个例子。假设我们要做个存储结构,需要存储下来三国中的人物,以及他们的详细信息。我们用他们的名字来作为存储的关键值,例如:刘备,曹操,孙权,关羽,张飞……等等。这个时候我们如果想用一般的方法来查找这些英雄豪杰,需要遍历整个存储空间,如果这些英雄豪杰一共有n个,那么这时候的时间算法复杂度为O(n)。显然如果n值很大,每次想要找到某个英雄就需要比较长的时间。

      此时我们先定义一个大的有序结构数组HashValue[index],用来存放各位英雄豪杰的信息。然后编写一个哈希函数ChangeToHashValue(name),函数的具体内容就不细说了,反正这个函数会将这些做为关键值的名字转换为HashValue[index]中的某个下标值x。然后可以将英雄的信息放进HashValue[x]中去。这样,可以将所有英雄的信息存储起来。当查询的时候再使用哈希函数ChangeToHashValue(name)得到这个下标值,这样就很容易得到了这个英雄的信息。例如:ChangeToHashValue(刘备)为10,那么就将刘备存储到HashValue[10]里面。当查询的时候再次使用ChangeToHashValue(刘备)得到10,这个时候我们就可以很容易找到刘备的所有信息。在实际应用中如果我们想把所有的英雄豪杰都存储进系统时,需要定义index>n。就是数组的大小要大于需要存储的信息量,所以说哈希表是一个以空间换取时间的数据结构。

     五、冲突问题:

          这个时候问题来了,出现了这种情况ChangeToHashValue(关羽)和ChangeToHashValue(张飞)得到的值是一样的,都是250,我们岂不是在存储过程中会遇到麻烦,怎么安排他们二位的地方呢(总不能让二位打一架,谁赢了谁呆在那吧),这就需要一个解决冲突的方法。当遇到这种情况时我们可以这样处理,先存储好了关羽,当张飞进入系统时会发现关羽已经是250了,那咱就加一位,251得了,这不就解决了。我们查找张飞的时候也是,一看250不是张飞,那就加个1,就找到了。这时还存在一个问题。直接用ChangeToHashValue(赵云)为251,张飞已经早早占了他的地方,那就再加1存到252呗。呵呵,这时我们会发现,当哈希函数冲突发生的机率很高时,可能会有一群英雄豪杰在250这个值后面扎堆排队。要命的是查找的时候,时间算法复杂度早已不是O(1)了(所以我们说理想情况下哈希表的时间算法复杂度为O(1))。 

      这就是说哈希函数的编写是哈希表的一个关键问题,会涉及到一个存储值在哈希表中的统计分布。如果哈希函数已经定义好了,冲突的解决就成为了改变系统性能的关键因素。其实还有很多种方法来解决冲突情况下的存储和查找问题,不一定非要线性向后排队,如果有好的哈希表冲突的解决方法也能很大程度上提高系统的效率。

    

分享到:
评论

相关推荐

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

    哈希表(Hashtable)是.NET框架中的一种常用数据结构,主要用作键值对存储,它提供了快速的数据存取方式。在WinForm应用程序中,我们可能会利用Hashtable来管理各种对象,尤其是在需要高效查找和操作数据时。下面将...

    HashTable

    《深入解析HashTable:C语言实现的精髓》 在计算机科学中,哈希表(HashTable)是一种数据结构,它实现了关联数组的抽象数据...理解这些核心概念和实现细节,有助于我们在实际开发中灵活应用哈希表,提高程序效率。

    hashtable存储数据.rar

    在Java编程语言中,`Hashtable`是一个非常基础且重要的数据结构...学习并理解`Hashtable`的工作原理和用法对于提升Java编程能力是非常有价值的。通过分析压缩包中的示例代码,你可以更好地掌握`Hashtable`的实际应用。

    c# asp.net hashtable对Datalist分页

    本篇文章将详细介绍如何利用C#中的Hashtable对象对Datalist进行分页处理。 首先,我们需要理解Datalist是ASP.NET提供的一种数据绑定控件,它可以用来显示列表或网格格式的数据。与GridView相比,Datalist提供了更多...

    asp.net遍历hashtable

    首先,理解Hashtable的基本概念至关重要。Hashtable继承自System.Collections字典类,它是一个非排序的、可变大小的键值对集合。键(Key)是唯一的,用于查找对应的值(Value)。在ASP.NET中,我们常常使用Hashtable...

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

    2. 性能:HashMap的性能比HashTable好,因为HashMap使用数组和链表来存储键值对,而HashTable使用链表来存储键值对。 3. null键:HashMap允许存放null键和null值,而HashTable不允许存放null键和null值。 常见面试...

    C#-Hashtable应用

    首先,让我们理解一下Hashtable的工作原理。Hashtable使用哈希表存储数据,通过计算键(key)的哈希码来定位元素的位置。由于哈希码是快速计算的,因此插入、查找和删除操作的时间复杂度通常为O(1),这使得Hashtable...

    HashMap和HashTable的区别和不同

    在Java编程中,`HashMap`与`HashTable`作为两种常用的数据结构,经常被用来存储键值对数据。尽管它们在功能上相似,但在实现细节、性能表现以及使用场景方面存在显著差异。本文将深入探讨两者之间的区别,帮助读者更...

    java Hashtable的泛型化

    通过理解并熟练运用`Hashtable`的泛型特性,我们可以编写出更安全、高效且易于维护的Java代码。在实际开发中,`HashMap`通常是首选,因为它的性能更好,但`Hashtable`在需要线程安全的情况下仍然是一个不错的选择。

    c#重写HashTable

    尽管如此,有时我们仍然需要对`HashTable`进行重写,以满足特定的需求或优化性能。以下将详细探讨如何在C#中重写`HashTable`以及相关知识点。 1. **理解HashTable** `HashTable`是一个基于开放寻址法的散列表实现...

    HashTable的java实现

    总的来说,理解哈希表的实现方式对于优化数据结构的性能至关重要。在Java中,除了`HashTable`,还有其他实现,如`HashMap`,它在单线程环境下提供了更好的性能,而`ConcurrentHashMap`则在多线程环境下提供高性能且...

    Hashtable的使用

    在Java编程语言中,`Hashtable`是一个基于键值对(key-value pairs)的数据结构,它属于同步的、线程安全的容器类。`Hashtable`是`Dictionary`类的一个子类,它不支持`null`键或`null`值。这个类实现了`Map`接口,...

    hashtable和dictionary的探讨

    在编程领域,哈希表(Hashtable)和字典(Dictionary)是两种常用的数据结构,它们在存储和检索键值对时提供了高效的性能。本文将深入探讨这两种数据结构的原理、性能差异以及实际应用中的考虑因素。 哈希表,通常...

    HashTable Sort

    其基本思想是利用 HashTable 的快速查找特性来对数据进行排序。具体而言,该方法首先将待排序的数据插入到 HashTable 中,在这个过程中可以附加一个顺序或值作为键或值的一部分;然后通过取出这些键或值并对其进行...

    C# .net HashTable

    **C# .NET HashTable 知识点详解** ...理解并熟练使用`HashTable`对于开发高效C# .NET应用程序至关重要。根据实际需求选择合适的数据结构,如在需要快速查找且不关心顺序的情况下,`HashTable`是一个不错的选择。

    HashTable 常用操作

    ### HashTable常用操作详解 #### 一、HashTable简介与.NET Framework中的实现 HashTable是一种非常重要的数据结构,在.NET ...通过学习这些知识点,开发者可以更好地理解和利用`Hashtable`来优化程序的性能。

    用Session、Hashtable实现购物车功能

    对于初学者,通过阅读这些代码可以更深入地理解Session和Hashtable在购物车功能中的应用。 总之,使用Session和Hashtable实现购物车功能是一种常见且实用的方法,它充分利用了Web服务器的存储能力,保证了用户在多...

    C#中哈希表(HashTable)用法实例详解(添加/移除/判断/遍历/排序等)

    哈希表(HashTable)在C#编程语言中是一种常用的数据结构,它允许高效地存储和检索键值对数据。在.NET Framework中,`System.Collections`命名空间提供了`HashTable`类,用于存储和管理这些键值对。下面我们将深入探讨...

    哈希表hashtable实现

    哈希表(Hash Table)是一种数据结构,它通过计算元素的哈希值并将其映射到数组中的特定位置来存储和检索数据。...通过阅读和理解"hashtable.c"和"hashtable.h",我们可以深入了解这一核心数据结构的实现细节。

    哈希表 Hashtable的操作使用

    ### 哈希表(Hashtable)的操作使用 ...通过上述示例可以看出,`Hashtable`类提供了一系列有用的方法来帮助开发者有效地管理和操作键值对数据。理解这些基本操作对于在实际项目中高效使用哈希表是非常有帮助的。

Global site tag (gtag.js) - Google Analytics