Dalam pemograman,hash
table adalah sebuah data structure yang meng-inplementasikan sebuah “associative
array abstract data type”, sebuah structure yang dapat memetakan kata kunci
menjadi value .hash table menggunakan fungsi hash untuk mendapatkan sebuah
index yang juga disebut hash code ,ke array of buckets atau slots yang dimana
value yang dicari bisa ditemukan.
Hashing adalah
sebuah Teknik yang mengubah vlue value
menjadi sebuah Panjang dari index of array .kita akan mengmodulokan
untuk mendapatkan range of key values .anggap contoh dari hash table dengan
besar 20 dan item item berkut disimpan item didalam (key,value) format.
- (1,20)
- (2,70)
- (42,80)
- (4,25)
- (12,44)
- (14,32)
- (17,11)
- (13,78)
- (37,98)
|
Sr.No.
|
Key
|
Hash
|
Array Index
|
|
1
|
1
|
1 % 20
= 1
|
1
|
|
2
|
2
|
2 % 20
= 2
|
2
|
|
3
|
42
|
42 % 20
= 2
|
2
|
|
4
|
4
|
4 % 20
= 4
|
4
|
|
5
|
12
|
12 % 20
= 12
|
12
|
|
6
|
14
|
14 % 20
= 14
|
14
|
|
7
|
17
|
17 % 20
= 17
|
17
|
|
8
|
13
|
13 % 20
= 13
|
13
|
|
9
|
37
|
37 % 20
= 17
|
17
|
Linear probing
Seperti yang kita
lihat,kadang kadang hashing Teknik digunakan untuk membuat index of array yang
sudah digunakan.dala kasus itu kita bisa mencari lokasi kosong sselanjutnya sampai
menemukan tempat kosong .teknik ini dinamakan linear probing.
|
Sr.No.
|
Key
|
Hash
|
Array Index
|
After Linear Probing, Array Index
|
|
1
|
1
|
1 % 20
= 1
|
1
|
1
|
|
2
|
2
|
2 % 20
= 2
|
2
|
2
|
|
3
|
42
|
42 % 20
= 2
|
2
|
3
|
|
4
|
4
|
4 % 20
= 4
|
4
|
4
|
|
5
|
12
|
12 % 20
= 12
|
12
|
12
|
|
6
|
14
|
14 % 20
= 14
|
14
|
14
|
|
7
|
17
|
17 % 20
= 17
|
17
|
17
|
|
8
|
13
|
13 % 20
= 13
|
13
|
13
|
|
9
|
37
|
37 % 20
= 17
|
17
|
18
|
Secara sederhana,hashing
berarti mengubah string dengan Panjang berapa pun dan mengoutputnya dengan
output yang punya Panjang sama. Salah satu Cryptocurrency,bitcoin transaksi
yang terjadi diambil sebagai input dan algoritma hashing berjalan(bitcoin menggunakan
SHA-256) yang memberikan output dangan Panjang tetap.
Dalam pemograman
,binary tree adalah data struktur pohon dimana setiap nodenya mempunyai paling
banyak dua anak atau cabang,dimana dinamakan left child dan right child. Binary
tree node mempunyai bagian bagian berikut:
1.
Data
2.
Pointer
to left child
3.
Pointer
to right child
No comments:
Post a Comment