Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

Hash Table

Posted on Edited on In
Symbols count in article: 3.3k Reading time ≈ 3 mins.

雜湊結構

背景知識

OO
python基礎語法

理解問題

實作dict

Java

TC:
O(1): set, get, delete
SC:
O(n): put, get, delete 

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
import java.util.*;
public class HashTable {
    private static void printTable(Hashtable hash_table){
        System.out.println("Table is: " + hash_table);
        System.out.println("Table size:" + hash_table.size());
    }
    public static void main(String args[]) {
        Hashtable<Integer,String> hash_table = 
        new Hashtable();
  
        // set
        hash_table.put(0, "Henry");
        hash_table.put(1, "Eric");
        hash_table.put(2, "Lunski");
        hash_table.put(3, "Shvara");
        System.out.println("Table Set");
        printTable(hash_table);
        
        //get
        System.out.println("Values at key 2 is:"+hash_table.get(2));
        
        // remove
        System.out.println("Delete key 0:"+ hash_table.remove(0));
        printTable(hash_table);
   }
}
>
java -cp /tmp/CSqCzH62b6 HashTable
Table Set
Table is: {3=Shvara, 2=Lunski, 1=Eric, 0=Henry}
Table size:4
Values at key 2 is:Lunski
Delete key 0:Henry
Table is: {3=Shvara, 2=Lunski, 1=Eric}
Table size:3

Python

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
class HashTable:
    def __init__(self, size):
        self.size = size
        self.hash_table = [[] for _ in range(self.size)]
  
    def set_val(self, key, val):
        
        # Get the bucket from hash function
        hashed_key = hash(key) % self.size
        bucket = self.hash_table[hashed_key]
  
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
              
            # key conflict
            if record_key == key:
                found_key = True
                break
  
        if found_key: # conflict update
            bucket[index] = (key, val)
        else: # not conflect append
            bucket.append((key, val))
  
    def get_val(self, key):
 
        # Get the bucket from hash function      
        hashed_key = hash(key) % self.size
        bucket = self.hash_table[hashed_key]
  
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
              
            # key conflict
            if record_key == key:
                found_key = True
                break
  
        if found_key:
            return record_val
        else:
            return "No record found"
  
    def delete_val(self, key):
        
        # Get the bucket from hash function
        hashed_key = hash(key) % self.size
        bucket = self.hash_table[hashed_key]
  
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
              
            # key conflict
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket.pop(index)
        return
  
    # To print the items of hash map
    def __str__(self):
        return "".join(str(item) for item in self.hash_table)
  
  
hash_table = HashTable(50)
  
# set
hash_table.set_val('0', 'henry')
hash_table.set_val('1', 'eric')
hash_table.set_val('2', 'lunski')
hash_table.set_val('3', 'shvara')
print(hash_table)
print()

# get
print(hash_table.get_val('2'))
print()

# delete
hash_table.delete_val('0')
print(hash_table)

>
[][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][('1', 'eric')][][][][][][][('3', 'shvara')][('2', 'lunski')][][][][][][('0', 'henry')]

lunski

[][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][('1', 'eric')][][][][][][][('3', 'shvara')][('2', 'lunski')][][][][][][]

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Welcome to my other publishing channels