Chapter 8 Symbol Table
səhifə 1/2 tarix 26.12.2016 ölçüsü 2,62 Mb. #3372
CHAPTER 8
Symbol Table
Search vs. Hashing hashing methods: hash functions types statistic hashing dynamic hashing
Static Hashing
mid-square (middle of square) division
Folding Partition the identifier x into several parts All parts except for the last one have the same length Add the parts together to obtain the hash address Two possibilities Shift folding x1=123, x2=203, x3=241, x4=112, x5=20, address=699 Folding at the boundaries x1=123, x2=203, x3=241, x4=112, x5=20, address=897
All the identifiers are known in advance M=1~999 X1 d11 d12 … d1n X2 d21 d22 … d2n … Xm dm1 dm2 … dmn Select 3 digits from n Criterion: Delete the digits having the most skewed distributions
Dostları ilə paylaş: