当前位置：网站首页>Introduction to hash table
Introduction to hash table
2022-07-27 06:26:00 【Envy only mandarin ducks, not immortals】
Catalog
2、 Hash table and hash function
Two 、 Hash table based on open hash
1、 Basic contents of hash table
4、 Lookup operation of hash table
One 、 Hash table export
1、 Example
The first unique character in a string
The first way of thinking , Use Map aggregate ：
First convert the string into a character array , stay Map<Character,Integer> Save characters in the set and the number of times characters appear , Traverse Map The number of collection fetches is 1 The corresponding key value , Traverse the string again , Find the corresponding index and solve it
public int firstUniqChar(String s) {
char[] data=s.toCharArray();
Map<Character,Integer> map=new HashMap<>();
for (char i:data){
map.put(i,map.getOrDefault(i,0)+1);
}
for (int i = 0; i < data.length; i++) {
if (map.get(data[i]) == 1) {
return i;
}
}
return -1;
}Save the number of occurrences of each character in an integer array , Finally, the number of times found is 1 Characters of
public int firstUniqChar(String s) {
// because s Contains only lowercase letters , Therefore, the frequency of each character is saved in the integer array
int[] arr=new int[26];
// Traversal string , Save the frequency of characters to arr Array
for (int i = 0; i <s.length() ; i++) {
char c=s.charAt(i);
// according to -‘a’ The rule of converts every lowercase letter to 26 One of the numbers
//'c'-'a'=2 'a'-'a'=0
arr[c-'a']++;
}
// Traversal string , stay arr A character with unique occurrence times is found in the array
int retindex=-1;
for (int i = 0; i < s.length(); i++) {
char c=s.charAt(i);
if (arr[c-'a']==1){
retindex=i;
break;
}
}
return retindex;
}2、 Hash table and hash function
The second method in the above example arr An array is a hash table , Every non repeating character corresponds to an integer number one by one , According to the rules （ character -‘a’） Convert each character to a number , This conversion operation is called hash function .
In the hash table, we need a method to convert any data type into the index of the array , Such a method is called hash function
Hash table is an array based extension , If you know the index in the array , You can go to O（1） Find the element within the time complexity , The hash table embodies the strategy of exchanging space for time
Example ：
In the array [9,5,2,7,3,6,8] Find out whether the element exists in ？
Just create a length of 10 Of arr Array , Iterate over the original array , If the element exists, it is arr Add... At the corresponding position of the array true
int[] arr=new int[10];
arr[9]=true;
arr[5]=true;
......... Until the entire set is scanned
You need to query at this time 7 Whether there is , Will judge arr[7] Is the value of true
In the above example , We open up the maximum value of the original array +1 New hash array , But when the span between the numbers of the original array is very large , Or contain negative numbers , This method doesn't work , such as [9,100000,-34,30000000,44] For this array , There is no way to create a hash array of indexes with one-to-one numbers .
3、 Hash Collisions
（1） Definition of hash conflict
When the number span of the original array is very large , You need to establish a mapping relationship between numbers and subscripts （hash function ）, Let a group of data with a large span be transformed into a group of data with a small span
Hash function can convert any data into index
For the original array with large data span , Generally speaking, the most common method we use to map any positive integer to a cell number is “ modulus ”
[10,20,30,40,50] It maps to [0,1,2,3,4] Modify the original array %4
10%4=2
20%4=0
30%4=2
40%4=0
50%4=2
Hash Collisions ： Different data get the same value after function calculation
The solution is to take a module of the original array prime number 7 That's all right.
（2） Solution to hash conflict
① Closed hash ： When there is a conflict , Find out whether there is a free location next to the conflicting location , Until you find the first free place to put the element （ It's hard to check and delete ）, When the hash table conflict is very serious , At this point, find an element from O(1) It becomes a traversal array O(n)
② Hash ： If hash conflict occurs , Let this position become a linked list , At this time, the hash table is array plus linked list
If an element position of the current hash table , Like 19 This position , It happens that many of the following elements are equal to 19, here 19 The linked list will be very long , Search efficiency will be reduced
resolvent ：
Expand the entire array （ The original array length 101, Download and expand to 102, The original %101 become %202）, At this time, many elements of the same linked list will be equally assigned to new positions , Reduced hash conflicts
Turn these two conflicting linked lists into a new hash table or binary search tree again , Just deal with the serious part of the conflict ,
Two 、 Hash table based on open hash
1、 Basic contents of hash table
public class MyHashMap {
// Number of effective nodes
private int size;
// The of the actual storage element Node Array
private Node[] hashtable;
// Take the modulus
private int M;
public MyHashMap(){
// Default initialization capacity
this(16);
}
public MyHashMap(int init){
// Initialize capacity
this.hashtable=new Node[init];
this.M=init;
}
/**
* Yes key Value for hash operation
* @param key
* @return
*/
public int hash(int key){
return Math.abs(key)%M;
}
}
class Node{
// Yes key Conduct hash operation
int key;
int value;
// Next node
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}2、 Adding hash table
/**
* Save a bunch of key value pairs to the hash table , if key Modify the original key value pair if it exists , Return the element before modification
* @param key
* @param val
*/
public int add(int key,int val){
// First pair key modulus , The value after taking the module is the index
int index=hash(key);
// Traverse index Corresponding linked list , see key Whether the value exists
for (Node x=hashtable[index];x!=null;x=x.next){
if (x.key==key){
int oldval=x.value;
x.value=val;
return oldval;
}
}
// At this time, the whole linked list does not contain the corresponding key value , Just insert the current linked list
Node node=new Node(key,val);
// The head node is hashtable[index]
node.next=hashtable[index];
hashtable[index]=node;
size++;
return val;
}3、 Expansion of hash table
When should we expand the capacity ？
When hash conflicts are serious , How to judge the severity of hash conflict , Introduce here Load factor
Load factor （LoadFactor）= The number of valid elements in the hash table / Hash table length
The larger the value of the load factor , That means the more serious the conflict , But the utilization rate of array is high （ There are many elements stored in the array ）, On the contrary, the smaller the load factor , It means that the smaller the conflict , The lower the utilization of arrays （ There are fewer elements stored in the array ）. The load factor is to take a balanced value in space and time .
For the expansion of array , When array length * Load factor <= When the number of effective elements , It needs to be expanded .
At this time, the load factor is added to the basic attributes of the hash table , Let's say it's 0.75
// Load factor
private static final double LoadFactor=0.75;
/**
* Save a bunch of key value pairs to the hash table , if key Modify the original key value pair if it exists , Return the element before modification
* @param key
* @param val
*/
public int add(int key,int val){
// First pair key modulus , The value after taking the module is the index
int index=hash(key);
// Traverse index Corresponding linked list , see key Whether the value exists
for (Node x=hashtable[index];x!=null;x=x.next){
if (x.key==key){
int oldval=x.value;
x.value=val;
return oldval;
}
}
// At this time, the whole linked list does not contain the corresponding key value , Just insert the current linked list
Node node=new Node(key,val);
// The head node is hashtable[index]
node.next=hashtable[index];
hashtable[index]=node;
size++;
// After adding elements, determine whether to expand
if (size>=hashtable.length*LoadFactor){
// Expansion method
Expansion();
}
return val;
}
/**
* Expansion method of hash table . By default, the length of the new array is doubled
*/
private void Expansion() {
// The length of the new array is twice that of the original
Node[] newHashTable=new Node[hashtable.length*2];
// Move all elements of the original array to the new array , The modulus value at this time M Change to the new array length
this.M=newHashTable.length;
// Move elements
// Traverse the hash table array
for (int i = 0; i <hashtable.length ; i++) {
// Traverse each small linked list
for (Node x=hashtable[i];x!=null;){
// Temporarily store the address of the next node
Node next=x.next;
// The index after the element is moved
int index=hash(x.key);
// Insert the header in the small linked list of the new array
x.next=newHashTable[index];
newHashTable[index]=x;
x=next;
}
}
hashtable=newHashTable;
}
4、 Lookup operation of hash table
/**
* Judge the present key Whether there is... In the table
* @param key
* @return
*/
public boolean containskey(int key){
int index=hash(key);
for (Node x=hashtable[index];x!=null;x=x.next){
if (x.key==key){
return true;
}
}
return false;
}
/**
* Judge value Whether there is
* @param val
* @return
*/
public boolean containsvalue(int val){
// Full table scan
for (int i=0;i<hashtable.length;i++){
for (Node x=hashtable[i];x!=null;x=x.next){
if (x.value==val){
return true;
}
}
}
return false;
}
/**
* Determine whether the key value pair exists
* @param key
* @param val
* @return
*/
public boolean containskeyval(int key,int val){
int index=hash(key);
for (Node x=hashtable[index];x!=null;x=x.next){
if (x.key==key&&x.value==val){
return true;
}
}
return false;
}5、 Delete hash table
**
* Delete hash table
* @param key
* @param val
* @return
*/
public boolean remove(int key,int val){
int index=hash(key);
// Determine whether the head node is to be deleted
Node head=hashtable[index];
if (head.key==key&&head.value==val){
// At this time, the head node is the node to be deleted
hashtable[index]=head.next;
head=head.next=null;
size--;
return true;
}
Node prev=head;
while (prev.next!=null){
if (prev.next.key==key&&prev.next.value==val){
// here prev It happens to be the precursor of the node to be deleted
Node cur=prev.next;
prev.next=cur.next;
cur=cur.next=null;
size--;
return true;
}else {
prev=prev.next;
}
}
// The current node cannot be found in the hash table
throw new NoSuchElementException("can't find node！cannot remove!");
}3、 ... and 、 Related codes
https://gitee.com/ren-xiaoxiong/rocket_class_ds/tree/master/src/hash边栏推荐
- How to choose the correct server backup method
- Thesis writing (harvest)
- 数据库的索引和事务（重点）
- Non photorealistic rendering (NPR) paper understanding and reproduction (unity) - stylized highlights for cartoon rendering and animation
- ROS topic name setting
- 英语基础知识：定语使用规则下篇
- Multi threaded CAS, synchronized lock principle, JUC and deadlock
- 软件测试用里篇
- 通信机制案例
- Introduction to Wireshark graphical interface
猜你喜欢
随机推荐
IP核之PLL
Detailed explanation of thread safety problems
学习软件测试时需要配备的运行环境需求搭建
Remote sensing image recognition training strategy
英语基础知识： 并列结构
Path to file
Remote sensing image recognition misclassification under multi class recognition
Chapter for software testing
Database commands
[first blog - outlook]
Introduction to JMeter
内部类的相关知识
数据库的约束以及设计
Summary of Internet simple protocol
测试基础概括
Launch file of ROS operation management
Pzk learns string function of C language (1)
Strategies for common locks in multithreading
ULCL功能--5GC
Learning records of programming -- Lesson 2 [first knowledge of C language]