Pengguna:LGA EGA/Tabel hash
Dalam komputasi, tabel hash, juga dikenal sebagai peta hash atau kumpulan hash, adalah struktur data yang mengimplementasikan array asosiatif, juga disebut kamus, yang merupakan tipe data abstrak yang memetakan kunci ke nilai . [1] Tabel hash menggunakan fungsi hash untuk menghitung indeks, juga disebut kode hash, ke dalam array keranjang atau slot, yang darinya nilai yang diinginkan dapat ditemukan. Selama pencarian, kunci di-hash dan hash yang dihasilkan menunjukkan di mana nilai terkait disimpan.
Dalam tabel hash berdimensi baik, kompleksitas waktu rata-rata untuk setiap pencarian tidak bergantung pada jumlah elemen yang disimpan dalam tabel. Banyak desain tabel hash juga memungkinkan penyisipan dan penghapusan pasangan kunci-nilai secara sewenang-wenang, dengan biaya rata-rata konstan per operasi yang diamortisasi . [2] [3] [4]
Hashing adalah contoh tradeoff ruang-waktu . Jika memori tidak terbatas, seluruh kunci dapat digunakan secara langsung sebagai indeks untuk menemukan nilainya dengan satu akses memori. Di sisi lain, jika tersedia waktu tak terbatas, nilai dapat disimpan tanpa memperhatikan kuncinya, dan pencarian biner atau pencarian linier dapat digunakan untuk mengambil elemen. [5] : 458
Hash table merupakan struktur data yang secara asosiatif menyimpan data. Dalam hal ini, data disimpan dalam format array, di mana setiap nilai data memiliki nilai indeks uniknya sendiri. Akses data akan menjadi sangat cepat jika Anda mengetahui indeks dari data yang diinginkan.
Dengan demikian, hash table menjadi struktur data di mana operasi penyisipan dan pencarian data terjadi sangat cepat terlepas dari ukuran data tersebut. Hash table menggunakan array sebagai media penyimpanan dan tekniknya untuk menghasilkan indeks suatu elemen yang dimasukkan atau ditempatkan.
Hash adalah suatu teknik “klasik” dalam Ilmu Komputer yang banyak digunakan dalam prakte secara mendalam. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Fungsi hash yang paling banyak digunakan dalam keamanan jaringan komputer dan internet adalah MD5 yang dirancang oleh Ron Rivest yang juga merupakan salah satu pengembang algoritma RSA pada tahun 1991. SHA dikembangkan oleh National Institute of Standards and Technology ( NIST ) dan National Security Agency ( NSA ) sebagai komponen Digital Signature Standart ( DSS )
Referensi
[[Kategori:Rekayasa perangkat lunak]]
- ^ Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, hlm. 81–98
- ^ Leiserson, Charles E. (Fall 2005). "Lecture 13: Amortized Algorithms, Table Doubling, Potential Method". course MIT 6.046J/18.410J Introduction to Algorithms. Diarsipkan dari versi asli tanggal August 7, 2009.
- ^ Knuth, Donald (1998). The Art of Computer Programming. 3: Sorting and Searching (edisi ke-2nd). Addison-Wesley. hlm. 513–558. ISBN 978-0-201-89685-5.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (edisi ke-2nd). MIT Press and McGraw-Hill. hlm. 221–252. ISBN 978-0-262-53196-2.
- ^ Kesalahan pengutipan: Tag
<ref>tidak sah; tidak ditemukan teks untuk ref bernamaalgo1rob