French
DeutschHash table - Simple English Wikipedia, the free encyclopedia
| Hash table | ||
|---|---|---|
| Type | Unsorted associative array | |
| Invented | 1952 | |
| Time complexity in big O notation | ||
| Average | Worst case | |
| Space | O(n)[1] | O(n) |
| Search | O(1 + n/k) | O(n) |
| Insert | O(1) | O(1) |
| Delete | O(1 + n/k) | O(n) |
A hash table is a type of tool for storing information. In computer science, these tools for keeping track of information, or data, are called data structures. A hash table is a data structure that uses a hash function to keep track of where data is. Each piece of information to be stored has a name, which is called a key. For example, a key might be a person's name. Each name is matched up to one piece of data called a value, like the person's telephone number.
The data is kept in another data structure called an array, which is like many boxes, or buckets, in a column to hold data. Each box has a number starting from 0 and counting up.
The idea behind a hash table is to find the box for a value using only its name. This means that no matter how many boxes there are, one can find information quickly by its name. It is very fast to use the box of an array by its number. A hash function reads a name and gives back a number. A hash table uses a hash function to find a box number for a name.
A good hash table will always find information at the same speed, no matter how much data is put in. A lot of hash tables also let the user put key/value pairs (a name and its data) in and take them out at the same speed.[2]
Because of this, hash tables can often find information faster than other tools, such as search trees or other table lookup structures. As a result, they are used in many kinds of computer software. They are used most often for associative arrays, databases, caches, and sets.
Uses
[change | change source]Many programming languages use hash tables, either as built-in associative arrays or as part of their standard library.
- .NET_Framework, which can be used from languages such as C# and VB.NET.[3]
- JavaScript[4]
- C++[5]
- Java[6]
- Python's built-in
dictimplements a hash table in the form of a type.[7] - Ruby[8]
- Rust[9]
- V (Vlang)[10]
References
[change | change source]- ↑ Thomas H. Cormen; et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press. pp. 253–280. ISBN 978-0-262-03384-8. Section 11: "Hash Tables".
- ↑ Donald Knuth (1998). 'The Art of Computer Programming'. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0. Section 6.4: "Hashing".
- ↑ "VB.NET HashSet Example". Dot Net Perls.
- ↑ "Map - JavaScript | MDN". developer.mozilla.org. 2023-06-20. Retrieved 2023-07-15.
- ↑ "Programming language C++ - Technical Specification" (PDF). International Organization for Standardization. pp. 812–813. Archived from the original (PDF) on 21 January 2022. Retrieved 8 February 2022.
- ↑ "Lesson: Implementations (The Java™ Tutorials > Collections)". docs.oracle.com. Archived from the original on January 18, 2017. Retrieved April 27, 2018.
- ↑ Zhang, Juan; Jia, Yunwei (2020). "Redis rehash optimization based on machine learning". Journal of Physics: Conference Series. 1453 (1): 3. Bibcode:2020JPhCS1453a2048Z. doi:10.1088/1742-6596/1453/1/012048. S2CID 215943738.
- ↑ Jonan Scheffler (December 25, 2016). "Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding". heroku.com. Archived from the original on July 3, 2019. Retrieved July 3, 2019.
- ↑ "doc.rust-lang.org". Archived from the original on December 8, 2022. Retrieved December 14, 2022.
- ↑ Rao, Navule Pavan Kumar (December 10, 2021). Getting Started with V Programming. p. 103. ASIN B09FKK3JL7. ISBN 978-1839213434. OCLC 1290492862.