哈希表(hashtable)的javascript简单实现

首先简单的介绍关于属性的一些方法:
属性的枚举:
for/in循环是遍历对象属性的方法。如

javascript中没有像c#,java那样的哈希表(hashtable)的实现。在js中,object属性的实现就是hash表,因此只要在object上封装点方法,简单的使用obejct管理属性的方法就可以实现简单高效的hashtable。

一、哈希表(hashtable)简述

c/c++ 哈希表 hashtable

复制代码 代码如下:

首先简单的介绍关于属性的一些方法:

在.net
framework中,hashtable是system.collections命名空间提供的一个容器,用于处理和表现类似key/value的键值对,其中key通常可用来快速查找,同时key是区分大小写;value用于存储对应于key的值。hashtable中key/value键值对均为object类型,所以hashtable可以支持任何类型的key/value键值对.

概念:用key去查找value

实现hash函数有很多方法,本文用除留余数法。

var obj = {
name : ‘obj1’,
age : 20,
height : ‘176cm’
}
var str = ”;
for(var name in obj)
{
str += name + ‘:’ + obj[name] + ‘\n’;
}
alert(str);

属性的枚举:

二、哈希表的简单操作

除留余数法的概念:

取一个固定的基数的余数,注意不能用偶数,用偶数的话,分布会不均匀

发生冲突时,用链地址法解决

图形入图:

图片 1

#include <stdio.h>#include <malloc.h>#include <assert.h>#include <stdbool.h>#define ElemType int#define P 13typedef struct HashNode{  ElemType data;  struct HashNode* link;}HashNode;typedef HashNode* HashTable[P];void init_hash(HashTable ht){  for(int i = 0; i < P; ++i){    ht[i] = NULL;  }}int hash(ElemType key){  return key % P;}void insert_hash_table(HashTable ht, ElemType x){  int index = hash;  HashNode* s = (HashNode*)malloc(sizeof);  assert(s != NULL);  s->data = x;  //头插  s->link = ht[index];  ht[index] = s;}void show_hash_table(HashTable ht){  for(int i = 0; i < P; ++i){    printf("%d: ", i);    HashNode* p = ht[i];    while(NULL != p){      printf("%d->", p->data);      p = p->link;    }    printf;  }}HashNode* search_hash_table(HashTable ht, ElemType x){  int index = hash;  HashNode* p = ht[index];  while(NULL != p && p->data != x){    p = p->link;  }  return p;}bool remove_hash_node(HashTable ht, ElemType x){  HashNode* p = search_hash_table;  if(NULL == p)return false;  int index = hash;  HashNode* q = ht[index];  if{    ht[index] = p->link;    free;    return true;  }  while(q->link != p){    q = q->link;  }  q->link = p->link;  free;  return true;}int main(){  HashTable ht;  init_hash;  ElemType ar[] = {19,14,23,1,68,20,84,27,55,11,10,79};  int n = sizeof / sizeof;  for(int i = 0; i < n; ++i){    insert_hash_table(ht, ar[i]);  }  show_hash_table;  ElemType key = 68;  HashNode* p = search_hash_table;  if(NULL != p){    printf("%d\n", p->data);  }  remove_hash_node;  show_hash_table;  return 0;}

完整代码

输出为:name:obj1
  age:20
  height:176cm
检查属性是否存在:
in运算符可以用来测试一个属性是否存在。

for/in循环是遍历对象属性的方法。如:

在哈希表中添加一个key/value键值对:hashtableobject.add(key,value);
在哈希表中去除某个key/value键值对:hashtableobject.remove(key);
从哈希表中移除所有元素: hashtableobject.clear();
判断哈希表是否包含特定键key: hashtableobject.contains(key);
下面控制台程序将包含以上所有操作:
using system;
using system.collections; //使用hashtable时,必须引入这个命名空间
class hashtable
{
  public static void main()
  {
   Hashtable ht=new Hashtable();
   ht.Add(“a”,”a”);
   ht.Add(“b”,”b”);
   ht.Add(“c”,”c”);
   ht.Add(“e”,”e”);
   ht.Add(“d”,”d”);
   foreach(DictionaryEntry de in ht)
   {
    Console.WriteLine(de.Value);
   }
   Console.WriteLine(“———————————–“);
   string s=(string)ht[“a”];
   Console.WriteLine(“(string)ht[\”a\”]={0}”,s);
   s=ht[“a”].ToString();
   Console.WriteLine(“ht[\”a\”].ToString()={0}”,s);
   Console.WriteLine(“———————————–“);
   if(ht.ContainsKey(“e”))
   {
    Console.WriteLine(“Contains the key of \”e\””);
   }  
   ht.Remove(“e”);
   Console.WriteLine(“Remove(\”e\”)”);
   if(!ht.Contains(“e”))
   {
    Console.WriteLine(“It does not Contains the key of \”e\””);
   }
   Console.WriteLine(“———————————–“);
      ht.clear();//移除所有元素
      console.writeline(ht[“a”]); //此处将不会有任何输出
  }
}

复制代码 代码如下:

Copy to
Clipboard图片 2引用的内容:[www.bkjia.com] 1 var
obj = {
2 name : ‘obj1’,
3 age : 20,
4 height : ‘176cm’
5 }
6
7 var str = ”;
8 for(var name in obj)
9 {
10 str += name + ‘:’ + obj[name] + ‘\n’;
11 }
12 alert(str);

三,遍历哈希表

this.containsKey = function ( key )
{
return (key in entry);
}

输出为:name:obj1

遍历哈希表需要用到dictionaryentry object,代码如下:
foreach(dictionaryentry de in ht) //ht为一个hashtable实例
{
  console.writeline(de.key);//de.key对应于key/value键值对key
  console.writeline(de.value);//de.key对应于key/value键值对value
}

删除属性
使用delete运算符来删除一个对象的属性。使用delete删除的属性,for/in将不会枚举该属性,并且in运算符也不会检测到该属性。
delete entry[key];
delete obj.name;
下面是哈希表(hashtable)的js的实现方法:

  age:20

四,对哈希表进行排序

复制代码 代码如下:

  height:176cm

对哈希表进行排序在这里的定义是对key/value键值对中的key按一定规则重新排列,但是实际上这个定义是不能实现的,因为我们无法直接在hashtable进行对key进行重新排列,如果需要hashtable提供某种规则的输出,可以采用一种变通的做法:
arraylist akeys=new arraylist(ht.keys); //别忘了导入system.collections
akeys.sort(); //按字母顺序进行排序
foreach(string skey in akeys)
{
  console.write(skey + “:”);
  console.writeline(ht[skey]);//排序后输出
}

function HashTable()
{
var size = 0;
var entry = new Object();
this.add = function (key , value)
{
if(!this.containsKey(key))
{
size ++ ;
}
entry[key] = value;
}
this.getValue = function (key)
{
return this.containsKey(key) ? entry[key] : null;
}
this.remove = function ( key )
{
if( this.containsKey(key) && ( delete entry[key] ) )
{
size –;
}
}
this.containsKey = function ( key )
{
return (key in entry);
}
this.containsValue = function ( value )
{
for(var prop in entry)
{
if(entry[prop] == value)
{
return true;
}
}
return false;
}
this.getValues = function ()
{
var values = new Array();
for(var prop in entry)
{
values.push(entry[prop]);
}
return values;
}
this.getKeys = function ()
{
var keys = new Array();
for(var prop in entry)
{
keys.push(prop);
}
return keys;
}
this.getSize = function ()
{
return size;
}
this.clear = function ()
{
size = 0;
entry = new Object();
}
}

检查属性是否存在:

测试:
代码

in运算符可以用来测试一个属性是否存在。

复制代码 代码如下:

this.containsKey = function ( key )
{
return (key in entry);
}

<!DOCTYPE html PUBLIC “-//W3C//DTD XHTML 1.0 Transitional//EN”
“;
<html xmlns=”;
<head>
<title>HashTable</title>
<script type=”text/javascript”
src=”/js/jquery.js”></script>
<script type=”text/javascript”
src=”/js/HashTable.js”></script>
<script type=”text/javascript”>
function MyObject(name)
{
this.name = name;
this.toString = function(){
return this.name;
}
}
$(function(){
var map = new HashTable();
map.add(“A”,”1″);
map.add(“B”,”2″);
map.add(“A”,”5″);
map.add(“C”,”3″);
map.add(“A”,”4″);
var arrayKey = new Array(“1″,”2″,”3″,”4”);
var arrayValue = new Array(“A”,”B”,”C”,”D”);
map.add(arrayKey,arrayValue);
var value = map.getValue(arrayKey);
var object1 = new MyObject(“小4”);
var object2 = new MyObject(“小5”);
map.add(object1,”小4″);
map.add(object2,”小5″);
$(‘#console’).html(map.getKeys().join(‘|’) + ‘<br>’);
})
</script>
</head>
<body>
<div id=”console”></div>
</body>
</html>

删除属性

javascript hashtable实现代码
//www.jb51.net/article/20372.htm

使用delete运算符来删除一个对象的属性。使用delete删除的属性,for/in将不会枚举该属性,并且in运算符也不会检测到该属性。

您可能感兴趣的文章:

  • js中哈希表的几种用法总结
  • JavaScript中实现键值对应的字典与哈希表结构的示例
  • js实现HashTable(哈希表)的实例分析
  • javascript实现获取字符串hash值
  • 浅谈js多维数组和hash数组定义和使用
  • javascript
    hashtable实现代码
  • js数组去重的hash方法
  • js模拟hashtable的简单实例
  • js实现hashtable的赋值、取值、遍历操作实例详解
  • JS模拟实现哈希表及应用详解

1 delete entry[key];
2 delete obj.name;

下面是哈希表(hashtable)的js的实现方法:

Copy to
Clipboard图片 3引用的内容:[www.bkjia.com] 1
function HashTable()
2 {
3 var size = 0;
4 var entry = new Object();
5
6 this.add = function (key , value)
7 {
8 if(!this.containsKey(key))
9 {
10 size ++ ;
11 }
12 entry[key] = value;
13 }
14
15 this.getValue = function (key)
16 {
17 return this.containsKey(key) ? entry[key] : null;
18 }
19
20 this.remove = function ( key )
21 {
22 if( this.containsKey(key) && ( delete entry[key] ) )
23 {
24 size –;
25 }
26 }
27
28 this.containsKey = function ( key )
29 {
30 return (key in entry);
31 }
32
33 this.containsValue = function ( value )
34 {
35 for(var prop in entry)
36 {
37 if(entry[prop] == value)
38 {
39 return true;
40 }
41 }
42 return false;
43 }
44
45 this.getValues = function ()
46 {
47 var values = new Array();
48 for(var prop in entry)
49 {
50 values.push(entry[prop]);
51 }
52 return values;
53 }
54
55 this.getKeys = function ()
56 {
57 var keys = new Array();
58 for(var prop in entry)
59 {
60 keys.push(prop);
61 }
62 return keys;
63 }
64
65 this.getSize = function ()
66 {
67 return size;
68 }
69
70 this.clear = function ()
71 {
72 size = 0;
73 entry = new Object();
74 }
75 }

测试:

Copy to
Clipboard图片 4引用的内容:[www.bkjia.com]
<!DOCTYPE html PUBLIC “-//W3C//DTD XHTML 1.0 Transitional//EN”
“;

<html xmlns=”;
<head>
<title>HashTable</title>
<script type=”text/javascript”
src=”/js/jquery.js”></script>
<script type=”text/javascript”
src=”/js/HashTable.js”></script>
<script type=”text/javascript”>
function MyObject(name)
{
this.name = name;
this.toString = function(){
return this.name;
}
}

$(function(){
var map = new HashTable();
map.add(“A”,”1″);
map.add(“B”,”2″);
map.add(“A”,”5″);
map.add(“C”,”3″);
map.add(“A”,”4″);

var arrayKey = new Array(“1″,”2″,”3″,”4”);
var arrayValue = new Array(“A”,”B”,”C”,”D”);
map.add(arrayKey,arrayValue);
var value = map.getValue(arrayKey);

var object1 = new MyObject(“小4”);
var object2 = new MyObject(“小5”);

map.add(object1,”小4″);
map.add(object2,”小5″);

$(‘#console’).html(map.getKeys().join(‘|’) + ‘<br>’);
})

</script>
</head>
<body>
<div id=”console”></div>
</body>
</html>

相关文章