unit 1.pptx for advanced cloud computing unit

rgrgeggg

1. 19PCSPC101 ADVANCED DATA STRUCTURES AND ALGORITHMS UNIT-I

2. HASHING Dictionaries: Definition, Dictionary Abstract Data Type, Implementation of Dictionaries. Hashing: Review of Hashing, Hash Function, Collision Resolution Techniques in Hashing, Separate Chaining, Open Addressing, Linear Probing, Quadratic Probing, Double Hashing, Rehashing, Extendible Hashing.

3. Data Structure A data structure is a specialized format for organizing, processing , retrieving and storing data. While there are several basic and advanced structure types, any data structure is designed to arrange data to suit a specific purpose so that it can be accessed and worked with in appropriate ways. 2

4. Data Structure In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms. Each data structure contains information about the data values, relationships between the data and functions that can be applied to the data. 3

5. 5 Data Structure The data structure is basically a technique of organizing and storing of different types of data items in computer memory. It is considered as not only the storing of data elements but also the maintaining of the logical relationship existing between individual data elements. The Data structure can also be defined as a mathematical or logical model , which relates to a particular organization of different data elements.

6. 6 Data Structure Data: Data is the basic entity of fact that is used in calculations or manipulation process. The w a y o f o r g a n i z i n g of t h e d a t a & p erf o r m i ng t h e operations is called as data structure. Data structure=organized data+ operations Operations Insertion Deletions Searching Traversing

7. 7 Data Structure The organization must be convenient for users. D a t a s t r u c t u r es a r e im p l e m e n t ed i n t h e r e al tim e in the following situations: Car park File storage Machinery Shortest path Sorting Networking Evaluation of expressions

8. Data Structure Specification of data structure : Data structures are considered as the main building blocks of a computer program . Organization of data Accessing methods Degree of associativity Processing alternatives for information 8

9. Data Structure at the time of selection of data structure we should follow these two things so that our selection is efficient enough to solve our problem. The data structure must be powerful enough to handle the different relationship existing between the data. The structure of data also to be simple , so that we can efficiently process data when required. 9

10. 10 Characteristics of data structures Linear or non-linear: This characteristic describes whether the data items are arranged in chronological sequence, such as with an array , or in an unordered sequence, such as with a graph .

11. Characteristics of data structures Homogeneous or non-homogeneous: This characteristic describes whether all data items in a given repository are of the same type or of various types. 11

12. Characteristics of data structures Static or dynamic: This characteristic describes how the data structures are compiled. Static data structures have fixed sizes , structures and memory locations at compile time. Dynamic data structures have sizes, structures and memory locations that can shrink or expand depending on the use. 12

13. Types of data structures These data structures are directly operated upon by the machine instructions. 13

14. 14 Types of data structures Primitive data structure : The p r i mit i ve d ata str u c t ures a re k n o w n a s basic data structures. The s e d a ta st r uc t ures a r e dir e ctly o p era t e d upon by the machine instructions . The primitive data structures have different representation on different computers.

15. 15 Types of data structures Non-Primitive data structure : The non-primitive data structures are highly developed complex data structures. Basically t h ese are d e v el o p e d f r o m t h e primitive data structure. – The non-primitive da t a responsible for organizing the g r o u p str u c ture is of h o m o g e n e o us a nd he t er o g e n e o us da t a elements.

16. Types of data structures Data structure types are determined by what types of operations are required or what kinds of algorithms are going to be applied. Arrays- An array stores a collection of items at adjoining memory locations. Items that are the same type get stored together so that the position of each element can be calculated or retrieved easily. Arrays can be fixed or flexible in length. 16

17. Types of data structures Arrays- 17

18. Types of data structures S tac k s - 18

19. Types of data structures Queues - – A queue stores a collection of items similar to a stack; however the operation order can only be first in first out. 19

20. Types of data structures Linked lists- – A linked list stores a collection of items in a linear order. Each element or node in a linked list contains a data item as well as a reference or link to the next item in the list. 20

21. Types of data structures Trees- A tree stores a collection of items in an abstract hierarchical way. Each node is linked to other nodes and can have multiple sub- values also known as children. 21

22. Types of data structures A Tree has the following characteristics : The top item in a hierarchy of a tree is referred as the root of the tree. The remaining data elements are partitioned into a number of mutually exclusive subsets and they itself a tree and are known as the subtree . Unlike natural trees trees in the data structure always grow in length towards the bottom. 22

23. Types of data structures Graphs- A graph stores a collection of items in a non-linear fashion. Graphs are made up of a finite set of nodes also known as vertices and lines that connect them also known as edges . T h e se a re us e ful f o r r e pr e s e n ti ng r ea l - li fe s y s te m s su c h a s computer networks. 23

24. 24 Types of data structures The different types of Graphs are : Directed Graph Non-directed Graph Connected Graph Non-connected Graph Simple Graph Multi-Graph

25. Types of data structures Tries- – A trie or keyword tree, is a data structure that stores strings as data items that can be organized in a visual graph. 25

26. 26 Types of data structures Hash tables- A hash table or a hash map stores a collection of items in an associative array that plots keys to values. A hash table uses a hash function to convert an index into an array of buckets that contain the desired data item. Overcoming the drawbacks of linear data structures hashing is introduced.

27. 27 Types of data structures Files : – Files contain data or information, st o r e d permanently in the secondary storage device such as Hard Disk and Floppy Disk. – It is u s e f u l w h e n w e h a v e to st o re a n d p r o ce ss a large amount of data. – A file st o r e d in a i d e n t ifi e d u si n g storage a d e v i c e is a lw a y s file n am e li k e HELL O . D A T o r T E X T NAM E. T XT a n d so on.

28. Types of data structures Files : – A file na m e no r m a lly c o n t a i n s a p ri ma ry a n d a secondary name which is separated by a dot(.) . 28

29. 29 Fundamentals of data structures : Fundamental Data Structures The following four data structures are used ubiquitously in the description of algorithms and serve as basic building blocks for realizing more complex data structures. Sequences (also called as lists) Dictionaries Priority Queues Graphs Dictionaries and priority queues can be classified under a broader category called dynamic sets . binary and general trees are very popular building blocks for implementing dictionaries and priority queues.

30. Fundamentals of data structures : Dictionaries A dictionary is a general-purpose data structure for storing a group of objects. A dictionary has a set of keys and each key has a single associated value . When presented with a key the dictionary will return the associated value. A dictionary is also called a hash , a map , a hashmap in different programming languages. 30

31. 30 29 Fundamentals of data structures : Dictionaries For example the results of a classroom test could be represented as a dictionary with pupil's names as keys and their scores as the values results = { 'Detra' : 17, 'Nova' : 84, 'Charlie' : 22, 'Henry' : 75, 'Roxanne' : 92, 'Elsa' : 29 } I nstead of u s ing the n u m e r ical ind e x o f the data w e can use t h e dictionary names to return values >>> results['Nova'] 84 >>> results['Elsa']

32. 32 Fundamentals of data structures : Dictionaries The keys in a dictionary must be simple types (such as integers or strings) while the values can be of any type. Different languages enforce different type restrictions on keys and values in a dictionary. Dictionaries are often implemented as hash tables. Keys in a dictionary must be unique an attempt to create a duplicate key will typically overwrite the existing value for that key.

33. 33 Fundamentals of data structures : Dictionaries Di c ti on a ry is a n a b s t r ac t d a ta s tr u c t u re th a t s u p po r t s the following operations: search(K key) (returns the value associated with the given key) insert(K key, V value) delete(K key) Each element stored in a dictionary is identified by a key of type K. Dictionary represents a mapping from keys to values.

34. 34 Fundamentals of data structures : Dictionaries Dictionaries have numerous applications. contact book key: name of person; value: telephone number table of program variable identiers key: identier; value: address in memory property-value collection key: property name; value: associated value natural language dictionary key: word in language X; value: word in language Y etc

35. 35 Fundamentals of data structures : operations on dictionaries Dictionaries typically support several operations: retrieve a value (depending on language, attempting to retrieve a missing key may give a default value or throw an exception) insert or update a value (typically, if the key does not exist in the dictionary, the key-value pair is inserted; if the key already exists, its corresponding value is overwritten with the new one) remove a key-value pair test for existence of a key Note that items in a dictionary are unordered, so loops over dictionaries will return items in an arbitrary order.

36. Fundamentals of data structures : Implementations on dictionaries sorted or unsorted simple implementations: sequences, direct addressing hash tables binary search trees (BST) AVL trees self-organising BST red-black trees (a,b)-trees (in particular: 2-3-trees) B-trees and other 36

37. 37 Fundamentals of data structures : The Dictionary ADT The abstract data type that corresponds to the dictionary metaphor is known by several names. Other terms for keyed containers include the names map, table, search table, associative array, or hash. Whatever it is called, the idea is a data structure optimized for a very specific type of search. Elements are placed into the dictionary in key/value pairs.

38. Fundamentals of data structures : The Dictionary ADT T o d o a r e tri e v a l, t h e u s e r s upp l i e s a k e y , a n d t h e container returns the associated value. Eac h k e y i d e n tifi e s on e e n t r y ; t h a t i s, eac h k e y is unique. d a ta is r e m ov e d fr o m a d i c ti o n a ry b y s p ec if y i n g t h e key for the data value to be deleted 38

39. 39 Fundamentals of data structures : Dictionary Implementation with Hash-Table H as h T a b l e i s a d a t a str u ct u r e w h ic h s t o r e d at a i n associative manner. In hash table, data is stored in array format where each data values has its own unique index value. Access of data becomes very fast if we know the index of desired data. a data structure in which insertion and search operations are very fast irrespective of size of data. Hash Table uses array as a storage medium and uses hash technique to generate index where an element is to be inserted or to be located from.

40. Fundamentals of data structures : Dictionary Implementation with Hash-Table H a s h i n g i s a t ec hn i qu e to c o nv e rt a r a ng e o f k e y values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. C on s i d e r a n e x a m p le o f h a s h t a b le o f s i z e 20 , a n d following items are to be stored. Item are in key, value format. 40

41. Fundamentals of data structures : Dictionary Implementation with Hash-Table 41

42. Fundamentals of data structures : Dictionary Implementation with Hash-Table Linear Probing the hashing technique used create already used index of the array. In such case, we can search the next empty location in the array by looking into the next cell until we found an empty cell. This technique is called linear probing 42

43. Fundamentals of data structures : Dictionary Implementation with Hash-Table 43

44. Fundamentals of data structures : Dictionary Implementation with Hash-Table Following are basic primary operations of a hashtable which are following. Search − search an element in a hashtable. Insert − insert an element in a hashtable. delete − delete an element from a hashtable DataItem Define a data item having some data, and key based on which search is to be conducted in hashtable. struct DataItem { int data; int key; } ; 44

45. Fundamentals of data structures : Dictionary Implementation with Hash-Table H a sh M e th o d D e fi n e a h a s h i n g m e t ho d to c o m pu t e the hash code of the key of the data item. int hashCode(int key) { return key % SIZE; } 45

46. Fundamentals of data structures : Dictionary Implementation with Hash-Table Insert Operation Whenever an element is to be inserted. Compute the hash code of the key passed and locate the index using that hashcode as index in the array. Use linear probing for empty location if an element is found at computed hash code. 46

47. Fundamentals of data structures : Dictionary Implementation with Hash-Table Insert Operation 47

48. Fundamentals of data structures : Dictionary Implementation with Hash-Table D e l e te O p er a ti o n W h e n e v e r a n e l eme n t is t o b e deleted. Compute the hash code of the key passed and locate the index using that hashcode as index in the array. Use linear probing to get element ahead if an element is not found at computed hash code. W h e n f o u nd , st o re a du mm y it e m t h e re to ke e p performance of hashtable intact 48

49. Fundamentals of data structures : Dictionary Implementation with Hash-Table 49

50. Fundamentals of data structures : Dictionary Implementation with Hash-Table S e a r c h Op e r a t i o n W h e n e v e r a n e l eme n t is to b e searched. Compute the hash code of the key passed and locate the element using that hashcode as index in the array. Use li n ea r p r ob i n g t o g e t e l e m e n t a h e a d if e l e m en t not found at computed hash code. 50

51. Fundamentals of data structures : Dictionary Implementation with Hash-Table Search Operation 51

52. What is Hashing Widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets

53. Hash Functions simple/fast to compute, Avoid collisions have keys distributed evenly among cells Each uses a hash table for average complexity to insert , erase, and find in O(1) hash function is a one-to-one mapping between keys and hash values. So no collision occurs

54. characteristics of a good hash function The characteristics of a good hash function are as follows. It avoids collisions. It tends to spread keys evenly in the array. It is easy to compute (i.e., computational time of a hash function should be O(1)).

55. Collision Resolution Collision: when two keys map to the same location in the hash table. Collisions occur when two keys, k1 and k2, are not equal, but h(k1) = h(k2). Two ways to resolve collisions: Separate Chaining ( open hashing) Open Addressing (linear probing, quadratic probing, double hashing) ( closed hashing )

56. Several approaches for dealing with collisions are Example: K = {0, 1, ..., 199}, M = 10, for each key k in K, f(k) = k % M

57. Collision Resolution

58. o n . Collusion Resolution Methods Three methods in open addressing are linear probing, quadratic probing, and double hashing. These methods are of the division hashing method because the hash function is f( k) = k % M. Some other hashing methods are middle- square hashing method, multiplication hashing method, and Fibonacci hashing method, and so

59. Linear Probing Method The hash table in this case is implemented using an array containing M nodes, each node of the hash table has a field k used to contain the key of the node. M can be any positive integer but M is often chosen to be a prime number. When the hash table is initialized, all fields k are assigned to -1.

60. Linear Probing Method When a node with the key k needs to be added into the hash table, the hash function f( k) = k % M will specify the address i = f( k) (i.e., an index of an array) within the range [0, M - 1].

61. Linear Probing Method If there is no conflict, then this node is added into the hash table at the address i. If a conflict takes place, then the hash function rehashes first time f 1 to consider the next address (i.e., i + 1). If conflict occurs again, then the hash function rehashes second time f 2 to examine the next address (i.e., i + 2). This process repeats until the available address found then this node will be added at this address.

62. Linear Probing Method The rehash function at the time t (i.e., the collision number t = 1, 2, ...) is presented as follows When searching a node, the hash function f( k) will identify the address i (i.e., i = f( k)) falling between 0 and M - 1.

63. Linear Probing Method Let us consider a simple hash function as “key mod 7” and sequence of keys as 50, 700, 76, 85, 92, 73, 101. S t e p - 01: Draw the hash table For the given hash function, the possible range of hash values is [0, 6]. So, draw an empty hash table consisting of 7 buckets as

64. Linear Probing Method L e t u s c on si d e r a si m p l e h a s h f u n cti o n a s “ k e y m o d 7 ” and sequence of keys as 50, 700, 76, 85, 92, 73, 101. S t e p - 02: Insert the given keys in the hash table one by one. The first key to be inserted in the hash table = 50. Bucket of the hash table to which key 50 maps = 50 mod 7 = 1. So, key 50 will be inserted in bucket-1 of the hash table as

65. Linear Probing Method L e t u s c on si d e r a si m p l e h a s h f u n cti o n a s “ k e y m o d 7 ” and sequence of keys as 50, 700, 76, 85, 92, 73, 101. S t e p - 03: The next key to be inserted in the hash table = 700. Bucket of the hash table to which key 700 maps = 700 mod 7 = 0. So, key 700 will be inserted in bucket-0 of the hash table as-

66. Linear Probing Method L e t u s c on si d e r a si m p l e h a s h f u n cti o n a s “ k e y m o d 7 ” and sequence of keys as 50, 700, 76, 85, 92, 73, 101. S t e p - 04: The next key to be inserted in the hash table = 76. Bucket of the hash table to which key 76 maps = 76 mod 7 = 6. So, key 76 will be inserted in bucket-6 of the hash table as-

67. Linear Probing Method S t e p - 05: The next key to be inserted in the hash table = 85. Bucket of the hash table to which key 85 maps = 85 mod 7 = 1. Since bucket-1 is already occupied, so collision occurs. To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found. The first empty bucket is bucket-2. So, key 85 will be inserted in bucket-2 of the hash table as-

68. Linear Probing Method S t e p - 06: The next key to be inserted in the hash table = 92. Bucket of the hash table to which key 92 maps = 92 mod 7 = 1. Since bucket-1 is already occupied, so collision occurs. To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found. The first empty bucket is bucket-3. So, key 92 will be inserted in bucket-3 of the hash table as

69. Linear Probing Method S t e p - 07: The next key to be inserted in the hash table = 73. Bucket of the hash table to which key 73 maps = 73 mod 7 = 3. Since bucket-3 is already occupied, so collision occurs. To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found. The first empty bucket is bucket-4. So, key 73 will be inserted in bucket-4 of the hash table as-

70. Linear Probing Method S t e p - 08: The next key to be inserted in the hash table = 101. Bucket of the hash table to which key 101 maps = 101 mod 7 = 3. Since bucket-3 is already occupied, so collision occurs. To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found. The first empty bucket is bucket-5. So, key 101 will be inserted in bucket-5 of the hash table as

71. Linear Probing Method E xa m p l e : i n s e rt k e y s 32 , 53 , 22 , 92 , 1 7 , 34 , 24 , 37 , and 56 into a hash table of size M = 10 insert keys 32 into a hash table of size M = 10

72. Linear Probing Method 1 2 3 4 5 6 7 8 9 insert keys 32 into a hash table of size M = 10 i.e M-1=9 Hash Functions Distribute keys to locations in hash table Hash function is then applied to the integer value 32 such that it maps to a value between 0 to M-1 where M is the table size then modulo hashing is used Here k=32 M=10 f( k) = k % M f( k) = 32 % 10=2 will specify the address i = f( k) (i.e., an index of an array) within the range [0, M - 1]. Index position i =2 then insert 32 in 3 position

73. Linear Probing Method 1 2 32 3 4 5 6 7 8 9 insert keys 32 into a hash table of size M = 10 i.e M-1=9 Hash Functions Distribute keys to locations in hash table Hash function is then applied to the integer value 32 such that it maps to a value between 0 to M-1 where M is the table size then modulo hashing is used Here k=32 M=10 f( k) = k % M f( k) = 32 % 10=2 will specify the address i = f( k) (i.e., an index of an array) within the range [0, M - 1]. Index position i =2 then insert 32 in 3 position

74. Linear Probing Method 1 2 32 3 53 4 5 6 7 8 9 insert keys 53 into a hash table of size M = 10 i.e M-1=9 Hash Functions Distribute keys to locations in hash table Hash function is then applied to the integer value 53 such that it maps to a value between 0 to M-1 where M is the table size then modulo hashing is used Here k=53 M=10 f( k) = k % M f( k) = 53 % 10=3 will specify the address i = f( k) (i.e., an index of an array) within the range [0, M - 1]. Index position i =3 then insert 32 in 4 position

75. Linear Probing Method 1 2 32 /22 3 53 4 5 6 7 8 9 insert keys 22 into a hash table of size M = 10 i.e M-1=9 Hash Functions Distribute keys to locations in hash table Hash function is then applied to the integer value 22 such that it maps to a value between 0 to M-1 where M is the table size then modulo hashing is used Here k=22 M=10 f( k) = k % M f( k) = 22 % 10=2 will specify the address i = f( k) (i.e., an index of an array) within the range [0, M - 1]. Index position i = then insert 32 in 2 position If a conflict takes place, then the hash function rehashes first time f 1 to consider the next address

76. Linear Probing Method 1 2 32 /22 3 53 4 5 6 7 8 9 insert keys 22 into a hash table of size M = 10 i.e M-1=9 Then must be probe (move) for one time for finding empty slot Here k=22 M=10 f( k) = k % M f( k) = 22 % 10=2 will specify the address i = f( k) (i.e., an index of an array) within the range [0, M - 1]. Index position i = then insert 32 in 2 position If a conflict takes place, then the hash function rehashes first time f 1 to consider the next address

77. Quadratic probing Qu a d r at i c p r o b i n g op e ra t es b y t ak i ng t h e or i g i nal values hash i n d ex a n d a d di n g of an arbitrary s uccess i v e q u a d ratic polynomial until an open slot is found. An example sequence using quadratic probing is:

78. Quadratic probing it better avoids the clustering problem that can occur with linear probing. Let h(k) be a hash function that maps an element k to an integer in [0,m-1], where m is the size of the table. Let the i th probe position for a value k be given by the function

79. Quadratic probing When a node with the key k needs to be added into the hash table, the hash function will specify the address i within the range [0, M - 1] (i.e., i = f( k))

80. Quadratic probing If there is no conflict, then this node is added into the hash table at the address i. I f a con f l i c t t akes p l a ce, t h e n t he ha s h f unc t i o n rehashes first time f 1 to consider the address f( k) + I f con f li c t occu r s ag a i n, t hen t he ha s h f unc t i on rehashes second time f 2 to examine the address f( k) + Th i s p r o c e s s r epe a t s un ti l t he av a i l a b l e ad d r e s s found then this node will be added at this address.

81. Quadratic probing The rehash function at the time t (i.e., the collision number t = 1, 2, ...) is presented as follows. When searching a node, the hash function f( k) will identify the address i (i.e., i = f( k)) falling between 0 and M - 1

82. Quadratic probing Example: insert the keys :76,40,48,5,20 Draw the hash table For the given hash function, the possible range of hash values is [0, 6]. So, draw an empty hash table consisting of 7 buckets as S t e p - 01:

83. Quadratic probing Example: insert the keys :76,40,48,5,20 S t e p - 01: Insert the given keys in the hash table one by one. The first key to be inserted in the hash table = 76. Bucket of the hash table to which key 76 maps = 76 mod 7 = 6. So, key 76 will be inserted in bucket-7 of the hash table as 76%7=6 1 2 3 4 5 6 76

84. Quadratic probing Example: insert the keys :76,40,48,5,20 The next key to be inserted in the hash table =40 Bucket of the hash table to which key 40 maps = 40 mod 7 = 5. So, key 40 will be inserted in bucket-6 of the hash table as S t e p - 02: 40%7=5 1 2 3 4 5 40 6 76

85. Quadratic probing Example: insert the keys :76,40,48,5,20 The next key to be inserted in the hash table =48 S t e p - 03: Bucket of the hash table to which key 48 maps = 48 mod 7 = 6. Since bucket-6 is already occupied, so collision occurs. To handle the collision, quadratic probing technique keeps probing until an empty bucket is found. 48+ %7=6 1 2 3 4 5 40 6 76

86. Quadratic probing Example: insert the keys :76,40,48,5,20 The next key to be inserted in the hash table =48 S t e p - 04: Bucket of the hash table to which key 48 maps = 48 mod 7 = 6. Since bucket-6 is already occupied, so collision occurs. To handle the collision, quadratic probing technique keeps probing until an empty bucket is found. The first empty bucket is bucket-0. So, key 48 will be inserted in bucket-0 of the hash table as- 48+ %7=49%7=0 48 1 2 3 4 5 40 6 76

87. Quadratic probing S t e p - 05: The next key to be inserted in the hash table = 5. Bucket of the hash table to which key 5 maps = 5 mod 7 =5 . Since bucket-5 is already occupied, so collision occurs. To handle the collision, quadratic probing technique keeps probing until an empty bucket is found The first empty bucket is bucket-2. So, key 5 will be inserted in bucket-2 of the hash table as- 48 1 2 5 3 4 5 40 6 76 5+ %7=6%7=6 5+ %7=9%7=2 5 %7=5 150

88. Quadratic probing S t e p - 05: The next key to be inserted in the hash table = 20. Bucket of the hash table to which key 20 maps = 20 mod 7 =6 . Since bucket-6 is already occupied, so collision occurs. To handle the collision, quadratic probing technique keeps probing until an empty bucket is found The first empty bucket is bucket-3. So, key 20 will be inserted in bucket-3 of the hash table as- 48 1 2 5 3 20 4 5 40 6 76 20+ %7=21%7=3 20+ %7=24%7=3 20 %7=6 151

89. Quadratic probing insert the keys 10, 15, 16, 20, 30, 25, 26, and 36 into a hash table of size M = 10

90. Chaining

91. Chaining

92. Chaining

93. Chaining

94. Double hashing

95. Double hashing

96. Extensible hashing It is a technique which handles a large amount of data. The data t o be p l aced i n t he h ash table is by extracting certain number of bits Ext e ns i b l e hash i n g g r ow a nd sh i n k simi l ar to B-tress In ex t e n sible h a shi n g r e fe r ri n g t he si z e o f dir e ct o r y the el e m e nts a r e to be plac e d in buckets.

97. Extensible hashing Extendible hashing uses a directory to access its buckets. This directory is usually small enough to be kept in main memory and has the form of an array with 2d entries, each entry storing a bucket address (pointer to a bucket). The variable d is called the global depth of the directory

98. Extensible hashing M ultiple d i rec t o r y e n t ries m ay p oint t o t h e same bucket. Every bucket has a local depth leqd. The difference between local depth and global depth affects overflow handling.

99. Extensible hashing Suppose that g=2 and bucket size = 3. Suppose that we have records with these keys and hash function h(key) = key mod 64:

100. Extensible hashing Suppose that we have records with these keys and hash function h(key) = key mod 64:

101. Extensible hashing Insert 1111 i.e 110111

102. Extensible hashing Insert 3333 i.e 000101

103. Extensible hashing Insert 1235 i.e 010011

104. Extensible hashing Insert 2378 i.e 000010 000010 111 1 1235 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 169 1212 3333 2378

105. Extensible hashing Insert 1212 i.e 111100 111100 1212 3333 2378 111 1 1235 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 170

106. Extensible hashing Insert 1456 i.e 110000 1 10000 111 1 1235 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 171 3333 2378 1212 1456

107. Extensible hashing Insert 2134 i.e 010110 010110 2378 111 1 1235 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 3333 1212 1456 2134

108. Extensible hashing Insert 2345 i.e 101001 101001 2378 111 1 1235 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 3333 1212 1456 2134 2345

109. Extensible hashing Insert 1111 i.e 110111 110111 2378 111 1 1235 1111 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 3333 1212 1456 2134 2345

110. Extensible hashing Insert 8231 i.e 100111 100111 1212 1456 3333 2345 2378 2134 111 1 1235 1111 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 175

111. Extensible hashing Insert 8231 i.e 100111 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 176

112. Extensible hashing Insert 8231 i.e 100111 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 177

113. Extensible hashing Insert 8231 i.e 100111 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 178

114. Extensible hashing Insert 2222 i.e 101110 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 179

115. Extensible hashing Insert 9999 i.e 001111 preparedy by p venkateswarlu dept of IT JNTUK-UCEV 180

116. Extensible hashing The b u c ket c a n ho l d t h e da t a of its gl ob al depth. If data in bucket is more than global depth then split the bucket and double the directory

117. Extensible hashing Consider we have to insert 1, 4, 5, 7, 8, 10 assume each page can hold 2 data entries (2 is the depth) Step 1: insert 1, 4

118. Extensible hashing Consider we have to insert 1, 4, 5, 7, 8, 10 assume each page can hold 2 data entries (2 is the depth) Step 2: insert 5 the bucket is full hence double the directory.

119. Extensible hashing Consider we have to insert 1, 4, 5, 7, 8, 10 assume each page can hold 2 data entries (2 is the depth) Step 3: insert 7 but as the depth is full we can not insert 7 here then double the directory and split the bucket. preparedy by p venkateswarlu dept of IT JNTUK-UCEV 184

120. Extensible hashing After insertion of 7 consider the last two bits

121. Extensible hashing Consider we have to insert 1, 4, 5, 7, 8, 10 assume each page can hold 2 data entries (2 is the depth) Step 4: insert 8 i.e 1000

122. Extensible hashing Consider we have to insert 1, 4, 5, 7, 8, 10 assume each page can hold 2 data entries (2 is the depth) Step 5: insert 10 i.e 1000