JavaScript数据结构——集合、字典和散列表

时间：2016-03-20 00:35:03 阅读：219 评论：0 收藏：0 [点我收藏+]

集合、字典和散列表都可以存储不重复的值。

在集合中，我们感兴趣的是每个值本身，并把它当作主要元素。在字典和散列表中，我们用 [键，值] 的形式来存储数据。

集合（Set 类）：[值，值]对，是一组由无序且唯一（即不能重复）的项组成的。

字典（Map 类）：[键，值]对，也称作映射，其中键名是用来查询特定元素的。

散列（HashTable类/HashMap 类）：[键，值]对，是Dictionary类的一种散列表实现方式。散列函数的作用是给定一个键值，然后返回值在表中的地址。散列算法的作用是尽可能快地在数据结构中找到一个值。

在一些编程语言中，还有一种叫作散列集合的实现。散列集合由一个集合构成，但是插入、移除或获取元素时，使用的是散列函数。实现散列集合的不同之处在于，不再添加键值对，而是只插入值而没有键。和集合相似，散列集合只存储唯一的不重复的值。

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

集合方法声明：

首先，使用对象来表示集合。

序号	方法	说明
1	add(value)	向集合添加一个新的项
2	remove(value)	从集合移除一个值
3	has(value)	如果值在结合中，返回 true，否则返回 false
4	clear ( )	移除集合中的所有项
5	size ( )	返回集合所包含元素的数量。与数组的 length 属性类似。
6	values ( )	返回一个包含集合中所有值的数组。

字典方法声明：

首先，使用对象来表示集合。

序号	方法	说明
1	set(key, value)	向字典中添加新元素
2	remove(key)	通过使用键值来从字典中移除键值对应的数据值
3	has(key)	如果某个键值存在于这个字典中，则返回 true，反之则返回 false
4	get(key)	通过键值查找特定的数值并返回
5	clear ( )	将这个字典中的所有元素全部删除
6	size ( )	返回字典中所包含元素的数量。与数组的 length 属性类似。
7	keys()	将字典所包含的所有键名以数组形式返回
8	values ( )	将字典所包含的所有数值以数组形式返回

散列方法声明：

首先，使用数组来表示集合。

三个基础方法：

在实现这三个方法之前，要实现的第一个方法是散列函数，它是 HashTable 类中的一个私有方法。

处理散列表的冲突：

有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突。处理冲突有几种方法：分离链接、线性探查和双散列法。

分离链接：包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是是解决冲突的最简单的方法，但是它在 HashTable 实例之外还需要额外的存储空间。

线性探查：当想向表中某个位置加入一个新元素的时候，如果索引为 index 的位置已经被占据了，就尝试 index+1 的位置。如果 index+1 的位置也被占据了，就尝试 index+2 的位置，以此类推。

一个表现良好的散列函数是由几个方面构成的：插入和检索元素的时间（即性能），当然也包括较低的冲突的可能。

原文：http://www.cnblogs.com/Ruth92/p/5296606.html

踩

(0)

评论一句话评论（0）

分享档案

更多>