Describes two hash functions. One was used to implement a randomized binary search tree and the other a hash function. Implementation details and empirical performance analysis are provided. A link to the full source code is also provided. The code is implemented in C++.
Table of Contents
- Introduction
- Hash Functions
- hash3
- Combination of hash functions
- Data Structures
- Randomized Binary Search Tree
Objectives and Key Themes
This article aims to present several hash functions and their practical application in implementing a randomized binary search tree (rBST) and a fast hash table. The focus is on demonstrating how these functions contribute to efficient data structures without delving into cryptographic security considerations. Key themes of the text include:- Hash function design and optimization
- Implementation of hash tables and randomized binary search trees
- Collision resolution techniques in data structures
- Balancing efficiency and complexity in data structure design
Chapter Summaries
Introduction
The introduction provides a general overview of hash functions and their significance in computer science, particularly in the context of hash tables. The article outlines the objectives and scope of the discussion, highlighting the focus on hash functions for data structure implementation rather than cryptographic security.Hash Functions
This section delves into the specifics of two hash functions: hash3 and a combination of existing hash functions. The hash3 function is presented with detailed code and an explanation of its design and experimental results. The second hash function, a combination of four functions, addresses collision resolution by using multiple hash functions and a linked list for remaining collisions.Data Structures
This section explores the application of the hash functions in constructing data structures: the randomized binary search tree (rBST) and a hash table. It details the implementation of these structures, focusing on collision resolution using linked lists and the key role of hash functions in balancing efficiency and complexity. The code snippets provided illustrate the implementation of insertion, lookup, and deletion operations within the rBST structure.Keywords
This article focuses on hash functions, data structures, randomized binary search trees, hash tables, collision resolution, efficiency, and complexity in the context of computer science. Key concepts explored include the design and optimization of hash functions, the implementation of efficient data structures, and the balance between efficiency and complexity in data structure design.
Final del extracto de 13 páginas
- subir
- Citar trabajo
- Dr. Roger Doss (Autor), 2013, On Some Hash Functions: Constructing a randomized binary search tree and a hash table, Múnich, GRIN Verlag, https://www.grin.com/document/209288
Leer eBook
