On Some Hash Functions: Constructing a randomized binary search tree and a hash table

Rapport Technique , 2013 , 13 Pages , Note: none

Informatique - Informatique appliquée

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.

• Université: Northcentral University
• Note: none
• Auteur: Dr. Roger Doss (Auteur)
• Année de publication: 2013
• Pages: 13
• N° de catalogue: V209288
• ISBN (ebook): 9783656374657
• ISBN (Livre): 9783656375050
• Langue: anglais
• mots-clé: some, hash, functions, constructing