数据结构入门-哈希表

哈希表 - javascript

简介

哈希表；名字中的hash意思是根据这个hash函数和查找关键字key；可以直接确定查找值所在位置；类似数组中的索引；下面看看基本的数据结构特性

  1. 数组：（顺序存储）线性数据结构，内存连续；除了在数组最后push一个新数据的复杂度为O(1)外，无论你在哪个位置插入新数据的复杂度都为o(n) ***(注)** 在C或者Java等其他语言中，数组大小是固定的且内存地址是连续的，不会进行动态扩容。而在JavaScript中，数组就是对象，可以理解为一个键值映射：var arr = [‘a’, ‘b’, ‘c’];基本上等价于var arr = {1: ‘a’, 2: ‘b’, 3: ‘c’};所以此数组非彼数组
    插入数据时，待插入位置的的元素和它后面的所有元素都需要向后移
    删除数据时，待删除位置后面的所有元素都需要向前移
  2. 链表:（链式存储，线性表）元素不之间连续，通过指针将一组零散的内存块串联起来；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度O(1)；链表中最常见的三种结构分别是单链表，双链表，循环链表；***(注)** 数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）
  3. 哈希表：哈希表又叫散列表；哈希表的插入、查询、删除效率都是非常高的，拉链法。简单来说，哈希表就是通过一个映射函数f(key)将一组数据散列存储在数组中的一种数据结构 ；当选择了一个哈希函数之后，有可能不同的数据会计算出相同的key；会有一些解决冲突的方法；

哈希表的实现是结合了数组和链表的特性；速度如下复杂度如下图所示

数据结构 根据关键字查找 根据索引查找 插入 删除
数组 O(n) O(1) O(n) O(n)
有序数组 O(logn) O(1) O(n) O(n)
链表 O(n) O(n) O(1) O(1)
有序链表 O(n) O(n) O(1) O(1)
双向链表 O(n) O(n) O(1) O(1)
二叉树（一般情况） O(logn) – O(logn) O(logn)
二叉树（最坏情况） O(n) – O(n) O(n)
平衡树 O(logn) O(logn) O(logn) O(logn)
排序二叉树 O(logn)~O(n) O(logn)~O(n) O(logn)~O(n) O(logn)~O(n)
哈希表 O(1) – O(1) O(1)

基本步骤

1
2
3
4
5
6
7
8
9
// 实现哈希表
   function HashTable() {
	// 属性，也就是表；
       this.storage = [];
       //存放了几个元素
       this.count = 0;
       //主要是为了计算ladFactor，当它大于0.75的话就要扩容；查找性能就会变低；或者减少容量
       this.limit = 7;
}

方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
//哈希函数
      HashTable.prototype.hashFunc = function (str, size) {
          var hashCode = 0;
          //霍纳算法，来计算hashCode的值
          //cats -> Unicode编码；
          for (let i = 0; i < str.length; i++) {
              hashCode = 37 * hashCode + str.charCodeAt(i)
          }
          // 取余3
          let index = hashCode % size;
          return index
      }
      
      //插入&修改操作
      HashTable.prototype.put = function (key, value) {
          // 1.根据key获取对应的index
          let index = this.hashFunc(key, this.limit);
          // 2.根据index去除bucket
          let bucket = this.storage[index];
          // 3.判断是否为空
          if (bucket == null) {
              bucket = [];
              this.storage[index] = bucket;
          }
          // 4.判断是否修改数据
          for (let i = 0; i < bucket.length; i++) {
              const tuple = this.storage[index];
              if (tuple[0] == key) {
                  tuple[1] = value;
                  return;
              }
          }
          // 5.进行添加操作
          bucket.push([key, value]);
          this.count += 1;

          // 6.判断是否需要扩容操作
          if (this.count > this.limit * 0.75) {
              this.resize(this.limit * 2);
          }
      }

//获取操作
      HashTable.prototype.get = function (key) {
          let index = this.hashFunc(key, this.limit);
          console.log(index);
          let bucket = this.storage[index];
          if (bucket == null) {
              return null;
          }
          for (let i = 0; i < bucket.length; i++) {
              const tuple = bucket[i];
              console.log(tuple);
              if (tuple[0] == key) {
                  return tuple[1]
              }
          }
          return null;
      }

      // 删除操作
      HashTable.prototype.remove = function (key) {
          let index = hashFunc(key, this, limit);
          let bucket = this.storage[index];
          if (bucket == null) {
              return null;
          }
          for (let i = 0; i < array.length; i++) {
              const tuple = array[i];
              if (tuple[0] == key) {
                  bucket.splice(i, 1);
                  this.count--;
                  if (this.count < 7 && this.count < this.limit * 0.25) {
                      this.resize(Math.floor(this.limit / 2))
                  }
                  return tuple[1]
              }
          }
          return null;
      }

      //扩容
      HashTable.prototype.resize = function (newLimt) {
          // 1.保存就的内容
          let oldStorage = this.storage;
          // 2.重置所有属性
          this.storage = [];
          this.count = 0;
          this.limit = newLimt;
          for (let i = 0; i < oldStorage.length; i++) {
              let bucket = oldStorage[i];
              if (bucket == null) {
                  continue;
              }
              // 3.取出所有数据，重新插入
              for (let j = 0; j < bucket.length; j++) {
                  let tuple = bucket[j];
                  this.put(tuple[0], tuple[1]);
              }
          }
      }
      
      var s = new HashTable();
  	s.put('name', '1')
  	s.put('name', '2')
  	s.put('name', '3')
  	s.put('age', '4')
  	console.log(s.get('age'));

这里的解决冲突主要使用链地址法，这里将链地址法简化成了数组；常见的哈希函数是除留取余法； H(x) = x % p；假定哈希表长度为s,则p一般取不超过s的最大质数 ；就是上面例子用到的；
解决哈希冲突常见方法有可以百度一下；

数据结构
数据结构

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！