[笔记]算法复习笔记---数组、集合、散列表（下）

发表于 | 分类于
字数统计 1,506 | 阅读时长 6

散列表是一种空间换时间的数据结构，在算法中提升效率的一种常用的方法。但是，正如其特点，有时候所消耗的空间，真让人头疼，用的时候在二者之间权衡。

散列表，又叫哈希表（HashTable），是能够通过给定的关键字的值直接访问到具体对应值的数据结构。也就是说，把关键字映到一个表中的位置来直接访问记录，以加快访问速度。

通常，我们通过Key来找Value，也就是说，通过Key访问一个映射表来得到Value的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫做散列表。

如果可以通过不同的Key访问到同一个Value，那么就发生了碰撞，我们需要的是通过一个Key可以访问到唯一的Value。

常用的处理冲突的方法有：

  1. 开放地址法（开放寻址法）

    就是当这个key通过哈希函数找到存放value地址的位置，当这个位置已经存放数据，就存在其紧跟着后面没有占用的位置，如果超过了最大长度，对最大长度取余，这里移动的地址是产生冲突的偏移量。

  2. 再哈希法

    产生冲突后，用关键字其他部分继续计算地址，直到不产生冲突，当这种方法增加了时间。

  3. 链地址法

    当产生冲突，把处于同一地址的数据做成一个链表，这种方法最常见。

  4. 建立公共溢出区

    建立一个公共溢出区，把产生冲突的新地址放在这个公共溢出区里。

###散列表的特点：

  1. 访问速度快

    由于散列表有散列函数，把Key映射到一个地址上，访问key对映的Value时候，不需要查找，直接跳到那个地址，因此，散列表的增删改查等任何操作，速度都比较快。

  2. 需要额外的空间

    当发生冲突，需要额外的空间去存储，空间换时间，有舍才有得。

  3. 无序

    为了快速找到访问的元素，根据散列函数直接找到存储地址，访问速度就快起来，但是有序访问没有办法实现。

  4. 可能产生碰撞

没有完美的散列函数，无论如何总会产生冲突，采用冲突的处理办法，就会使散列表变得更加复杂。

下面展示如何实现一个散列表，这里用数组代替散列表元素（在在真实情况下，大多数语言的实现中，大多数元素都是一个特别的数组，每个元素对应一个地址），每个数组元素作为一个地址。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Entry {
 
		int key;
		int value;
		Entry  next;
		
		public Entry(int key, int value, Entry next) {
			super();
			this.key = key;
			this.value = value;
			this.next = next;
		}
		
}
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
public class HashTable {
	/**
	 * 默认散列表的初始长度
	 * 设置小一点，这样扩容的时候看的清楚
	 * 在实际使用中其实可以在初始化传参数，因为扩容是很消耗性能的
	 */
	private static final int DEFAULT_INITIAL_CAPACITY = 4;
	
	/**
	 * 扩容因子
	 */
	private static final float LOAD_FACTOR = 0.75f;
	
	/**
	 * 散列表数组
	 */
	private Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY];
	private int size = 0;
	private int use = 0;
	
	
	public void put(int key, int value) {
		int index = hash(key);
		if (table[index] == null) {
			table[index] = new Entry(-1, -1, null);
		}
		Entry e = table[index];
		
		if (e.next == null) {
			//不存在的值，向链表中添加，有可能扩容，要用table属性
			table[index].next = new Entry(key, value, null);
			size++;
			use++;
			//不存在的值，说明是个未用过的地址，需要判断是否扩容
			if (use >= table.length * LOAD_FACTOR) {
				resize();
			}
		}else {
			
			//本身存在的值，修改已有的值
			for (e = e.next; e != null; e =e.next) {
				int k = e.key;
				if (k == key) {
					e.value = value;
					return;
				}
			}
			//不存在相同的值，直接向链表中添加元素
			Entry temp = table[index].next;
			Entry newEntry = new Entry(key, value, temp);
			table[index].next = newEntry;
			size ++;
			
		}
	}
	/**
	 * 删除
	 * @param key
	 */
	public void remove( int key) {
		int index = hash(key);
		Entry e = table[index];
		Entry pre = table[index];
		if (e != null && e.next !=null) {
			for(e = e.next ; e != null; pre = e, e = e.next){
				int k = e.key;
				if (k == key) {
					pre.next = e.next;
					size --;
						return;
				}
			}
		}
	}
	/**
	 * 获取
	 */
	public int get(int key) {
		int index = hash(key);
		Entry e = table[index];
		if (e != null && e.next != null) {
			for (int i = 0; i < table.length; i++) {
				for (e = e.next; e != null; e =e.next) {
					int k = e.key;
					if (k == key) {
						return e.value;
					}
				}
			}
		}
		return -1;
	}
	
	/**
	 * 获取散列表中元素的个数
	 */
	public int size() {
		return size;
	}
	/**
	 * 本身散列表是不该有这个方法的，在这里只是为了清楚地看到确实扩容了。
	 * @return
	 */
	public int getLength() {
		return table.length;
	}
	
	
	
	/**
	 * 根据key，通过哈希函数获取位于散列表数组中的哪个位置
	 * @param key
	 * @return
	 */
	public int  hash(int key) {
		return key % table.length;
	}
	
	/**
	 * 扩容
	 */
	public void resize() {
		int newLength = table.length * 2;
		Entry[] oldTable = table;
		table = new Entry[newLength];
		use =0;
		
		for (int i = 0; i < oldTable.length; i++) {
			if (oldTable[i] != null && oldTable[i].next != null) {
				Entry entry = oldTable[i];
				while (null != entry.next) {
					Entry next = entry.next;
					//重新计算哈希值，放入新的地址
					int index = hash(next.key);
					if (table[index] == null) {
						use ++;
						table[index] = new Entry(-1, -1, null);
					}					
					table[index].next = new Entry(next.key, next.value, table[index].next);
					//可以用下面三行代替
//					Entry temp = table[index].next;
//					Entry newEntry = new Entry(next.key, next.value, temp);
//					table[index].next = newEntry;
					
					entry = next;
				}
			}
		}	
	}	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class HashTableTest {
	public static void main(String[] args) {
		HashTable hashTable = new HashTable();
		hashTable.put(1, 10);
		hashTable.put(2, 20);
		hashTable.put(5, 50);//和key为1的元素落在一个散列地址上了，实际使用长度为2
		
		System.out.println(hashTable.getLength());//散列表长度为4
		hashTable.put(3, 30);//总长度为4，加上该元素后长度就 大于等于3 了，所以扩容
		System.out.println(hashTable.getLength());//散列表长为8
		//在扩容后4个元素又分别落在不同的地址上
		hashTable.put(6, 60);//使用第5 个地址
		hashTable.put(7, 70);//使用第6个地址，为8的0.75倍，又需要扩容
		System.out.println(hashTable.getLength());//散列表长度为16
		System.out.println(hashTable.get(1));//10
		System.out.println(hashTable.get(3));//30
		System.out.println(hashTable.get(5));//50
		System.out.println(hashTable.get(6));//60
	}
}
世界再嘈杂，匠人的内心，绝对是必须是安静的、安定的。