hash table computer science Actions Cite verifiedCite While every effort has been made to follow citation style rules, there may be some discrepancies. Please refer to the appropriate style manual or other sources if you have any questions. Select Citation Style MLA APA Chicago Manual of Style Copy Citation Share Share Share to social media Facebook X URL https://www.britannica.com/topic/hash-table Give Feedback Feedback Corrections? Updates? Omissions? Let us know if you have suggestions to improve this article (requires login). Feedback Type Select a type (Required) Factual Correction Spelling/Grammar Correction Link Correction Additional Information Other Your Feedback Submit Feedback Thank you for your feedback Our editors will review what you’ve submitted and determine whether to revise the article.

　　Print Cite verifiedCite While every effort has been made to follow citation style rules, there may be some discrepancies. Please refer to the appropriate style manual or other sources if you have any questions. Select Citation Style MLA APA Chicago Manual of Style Copy Citation Share Share Share to social media Facebook X URL https://www.britannica.com/topic/hash-table Feedback Written by Stephen Eldridge Stephen Eldridge is a writer and editor of fiction and nonfiction for all ages. Stephen Eldridge Fact-checked by The Editors of Encyclopaedia Britannica Encyclopaedia Britannica's editors oversee subject areas in which they have extensive knowledge, whether from years of experience gained by working on that content or via study for an advanced degree. They write new content and verify and edit content received from contributors. The Editors of Encyclopaedia Britannica Last Updated: Nov 5, 2024 • Article History Table of Contents Ask the Chatbot a Question Ask the Chatbot a Question hash table, in computer science, a dictionary that maps keys to values using a hash function. A hash function is a mathematical function that maps data of arbitrary length to data of a fixed length. Hashing is a highly efficient way of performing certain operations, such as searches, insertions, and deletions. Hash functions are also widely used in cryptography, though not commonly in the form of hash tables.

　　A hash table allows stored data to be retrieved from a table more quickly than a simple binary search of the data would allow, because the key being searched for is used to directly identify the index (row, or record) in the table that should be returned. For example, suppose one has a hash table designed to allow one to input a name and return a phone number. The hash table uses an algorithm to convert the name to a value of a fixed length that serves as the index for the table. Thus, hashing the key directs you to a specific place in the table to find the desired information.

　　When more than one value is assigned to the same key, this is referred to as a collision. While collisions are not desirable, they are common and can be handled in different ways. One way is to have more than one value stored in a list at each index. This is called chaining. Multiple key values can be stored at the same index, and, when one of those keys is entered, it will be compared with the keys at the index until the correct one is found. Another method is called open addressing. In open addressing, when a collision occurs, one key is moved to a different open slot in the hash table based on a particular search algorithm.

　　With chaining, many keys can be divided among the indices. A key and its associated date can be deleted in the same way. Hashing can be effective at dividing up a large number of keys so that searches and other operations on even very large amounts of data go quickly.

　　A well-designed hash table can have a time complexity of O(1), or constant time, meaning that the same number of operations will be required to perform the search regardless of how many keys are in the table.