Data Structures (Session 9) - PDF
Document Details
Uploaded by PreciousHarpGuitar
Misr University for Science and Technology
Tags
Summary
This document covers data structures, specifically hash functions. It describes how hash functions work and provides examples. It also details different methods for hash functions like modulo functions and multiplication method. The document is part of Session 9.
Full Transcript
# علوم الحاسب ## الفرقة الثانية ### Session 9 ### هياكل البيانات ### Data Structures ## Q.1. What is hash function h(k)? A hash function is a function which gives a key and generates an address in the table. - Return number for an object. - Two equal objects have the same number. - Collision if d...
# علوم الحاسب ## الفرقة الثانية ### Session 9 ### هياكل البيانات ### Data Structures ## Q.1. What is hash function h(k)? A hash function is a function which gives a key and generates an address in the table. - Return number for an object. - Two equal objects have the same number. - Collision if different objects have the same hash code. - Solve the problem search in unsorted array O(1). Note: The Time Complexity in binary search (sorted array) is O(log n). ### HASH FUNCTION: | OBJECT | INTEGER | HASH CODES | TABLE INDEXES | | --------- | -------- | ----------- | --------------- | | obj1 | 4 | 4 | 4 | | obj2 | 16 | 1 | 1 | | obj3 | 68 | 3 | 3 | | obj4 | 125 | 0 | 0 | ##### HASH TABLE | | OBJ4 | OBJ2 | OBJ3 | OBJ1 | | - | ---- | ---- | ---- | ---- | | 0 | | | | | | 1 | | | | | | 2 | | | | | | 3 | | | | | | 4 | | | | | 1. Mod functions H(k)= k mode m. 2. Multiplication method H(k)=floor(m*(KA - floor(KA))) where A const A>0 and A <1 3. Universal hashing 1| Page
