js實現存儲對象的數據結構hashTable和list - fangsmile－IT工程師數位筆記本

文章出處

以下代碼是typescript語言來寫的，其實和es6面向對象的寫法基本一致。大家閱讀后都明白這些方法的作用。

hash

hash結構用于處理和表現類似key/value的鍵值對，其中key通常可用來快速查找，同時key是區分大小寫；value用于存儲對應于key的值。

實現該數據結構的幾個方法：

函數名	說明	返回值
set(key,value)	添加項	無
del(key)	根據key刪除一項	無
has(key)	是否包含某個key	bool
get(key)	根據key值獲取value	value
first()	獲取第一個value	value
last()	獲取最后一個value	value
count()	獲取項總數	int
all()	返回所有值的數組	array
getByIndex(index)	根據在數組中的index順序獲取value	value
foreach(callback)	遍歷所有值	無
indexOf(key)	根據key值獲取在數組中的順序值	index，int
insertAt(index,value,key)	在指定index位置插入key，value	無

  1   export class HashTable<T> {
  2         private items: { [key: string]: HashValue<T> };
  3         @SerializeProperty({ list: true, type: Array })
  4         private itemList: Array<T>;
  5         constructor() {
  6             super();
  7             this.items = {};
  8             this.itemList = [];
  9         }
 10 
 11         set(key: string, value: T): void {
 12             var vl = new HashValue<T>();
 13             vl.key = key;
 14             vl.value = value;
 15             var index = this.itemList.length;
 16             if (this.has(key)) {
 17                 index = this.items[key].index;
 18             }
 19             vl.index = index;
 20             this.itemList[index] = value;
 21             this.items[key] = vl;
 22         }
 23 
 24         del(key: string): void {
 25             if (this.has(key)) {
 26                 var index = this.items[key].index;
 27                 if (index > -1) {
 28                     this.itemList.splice(index, 1);
 29                 }
 30                 delete this.items[key];
 31                 this.resetIndex();
 32             }
 33         }
 34 
 35         resetIndex(): void {
 36 
 37             this.foreach((k, v: T) => {
 38                 var index = this.itemList.indexOf(v);
 39                 this.items[k].index = index;
 40             });
 41         }
 42 
 43         has(key: string): boolean {
 44             return key in this.items;
 45         }
 46 
 47         get(key: string): T {
 48             if (this.has(key)) {
 49                 return this.items[key].value;
 50             }
 51             return null;
 52         }
 53 
 54         count(): number {
 55             return this.itemList.length;
 56         }
 57 
 58         all(): Array<T> {
 59             return this.itemList;
 60         }
 61 
 62         first() {
 63             return this.itemList[0];
 64         }
 65 
 66         last() {
 67             return this.itemList[this.itemList.length - 1];
 68         }
 69 
 70         getByIndex(index: number): T {
 71             return this.itemList[index];
 72         }
 73 
 74         //遍歷 擴展
 75         foreach(callback) {
 76             for (var key in this.items) {
 77                 callback(key, this.items[key].value);
 78             }
 79         }
 80 
 81         //獲取index
 82         indexOf(key) {
 83             if (this.has(key)) {
 84                 return this.items[key].index;
 85             }
 86         }
 87 
 88         //插入
 89         insertAt(index: number, value: T, key: string) {
 90             this.itemList.splice(index, 0, value);
 91             var hashV = new HashValue<T>();
 92             hashV.index = index;
 93             hashV.key = key;
 94             hashV.value = value;
 95             this.items[key] = hashV;
 96             this.resetIndex();
 97         }
 98 
 99         sort(callback: Function) {
100             this.itemList.sort((a: T, b: T) => { return callback(a, b);     
101           });
102         }
103     }

List

js實現鏈表List數據結構的幾個方法：

函數名	說明	返回值
add(value)	添加項	無
addList(list)	添加另一個集合	無
pop()	刪除最后一項并返回該項	value
shift()	刪除第一項并返回該項	value
remove(index)	根據索引值刪除某一項	無
removeMany(index,count)	刪除從指定位置開始的某幾項	無
clear()	刪除所有項	無
contains(value)	是否包含某個值	boolean
indexOf(value)	根據值獲取在數組中的順序值	int
get(index)	根據index獲取value	value
set(index,value)	設置index位置的value	無
length()	獲取項總數	int
all()	返回所有值的數組	array
foreach(callback)	遍歷所有值	無
reverseForeach(callback)	倒序遍歷所有值	無
sort(callback)	根據某個排序規則進行排序	無
insert(index,value)	在指定index位置插入value	無

 1  export class List<T> {
 2         private items: Array<T>;
 3 
 4         private checkIndex(index): boolean {
 5             return !(index < 0 || isNaN(index) || index >= this.items.length);
 6         }
 7         constructor() {
 8             super();
 9             this.items = new Array<T>();
10         }
11 
12         length(): number {
13             return this.items.length;
14         }
15 
16         add(value: T): void {
17             this.items.push(value);
18         }
19         addList(valueList: List<T>) {
20             for (var i = 0; i < valueList.length(); i++) {
21 
22                 var value = valueList.get(i);
23                 this.items.push(value);
24             }
25         }
26         pop(): T {
27             return this.items.pop();
28         }
29 
30         shift() {
31             this.items.shift();
32         }
33 
34         remove(index: number): void {
35             if (this.checkIndex(index)) {
36               this.items.splice(index,1);
37                 
38             }
39         }
40         /**
41          * 從指定索引處開始刪除指定個數的元素
42          * @param from 
43          * @param count 
44          */
45         removeMany(from: number, count: number) {
46 
47             if (this.checkIndex(from)) {
48                 this.items.splice(from, count);
49             }
50         }
51 
52         clear(): void {
53             this.items = [];
54         }
55 
56         contains(value: T): boolean {
57             for (var i in this.items) {
58                 return value == this.items[i];
59             }
60             return false;
61         }
62 
63         indexOf(value: T): number {
64             return this.items.indexOf(value);
65         }
66 
67         insert(index: number, value: T) {
68             //this.checkIndex(index) && this.items.splice(index , 0, value);
69             this.items.splice(index, 0, value);
70         }
71 
72         get(index: number): T {
73             return this.items[index];
74         }
75         set(index, value: T) {
76             this.items[index] = value;
77         }
78         all(): Array<T> {
79             return this.items;
80         }
81         foreach(callback:(i:number,item:T)=>any) {
82             var len = this.items.length;
83             for (var i = 0; i < len; i++) {
84                 if (callback(i, this.items[i]) === false) break;
85             }
86         }
87         reverseForeach(callback) {
88             var len = this.items.length;
89             for (var i = len - 1; i >= 0; i--) {
90                 if (callback(i, this.items[i]) === false) break;
91             }
92         }
93         sort(callback: Function) {
94             this.items.sort((a: T, b: T) => { return callback(a, b); });
95         }
96     }