const int digs const int mersennep ( <<digs int universalhashint xint aint bint long long hashval static_casta bhashval hashval >digs hashval mersennep )ifhashval >mersennep hashval -mersennepreturn static_casthashval mfigure simple implementation of universal hashing of two since the remainder could be almost as large as pthe resulting sum might be larger than pso we scale it back down at lines and universal hash functions exist for strings also firstchoose any prime plarger than (and larger than the largest character codethen use our standard string hashing functionchoosing the multiplier randomly between and and returning an intermediate hash value between and inclusive finallyapply universal hash function to generate the final hash value between and extendible hashing our last topic in this deals with the case where the amount of data is too large to fit in main memory as we saw in the main consideration then is the number of disk accesses required to retrieve data as beforewe assume that at any point we have records to storethe value of changes over time furthermoreat most records fit in one disk block we will use in this section if either probing hashing or separate chaining hashing is usedthe major problem is that collisions could cause several blocks to be examined during searcheven for well-distributed hash table furthermorewhen the table gets too fullan extremely expensive rehashing step must be performedwhich requires (ndisk accesses clever alternativeknown as extendible hashingallows search to be performed in two disk accesses insertions also require few disk accesses we recall from that -tree has depth (logm/ nas increasesthe depth of -tree decreases we could in theory choose to be so large that the depth of the -tree would be then any search after the first would take one disk accesssincepresumablythe root node could be stored in main memory the problem with this strategy is that the branching factor is so high that it would take considerable processing to determine which leaf the data was in if the time to perform this step could be reducedthen we would have practical scheme this is exactly the strategy used by extendible hashing