Chapter 8 Symbol Table



Yüklə 2,62 Mb.
səhifə1/2
tarix26.12.2016
ölçüsü2,62 Mb.
#3372
  1   2


CHAPTER 8


Symbol Table





Search vs. Hashing

  • Search tree methods: key comparisons

  • hashing methods: hash functions

  • types

    • statistic hashing
    • dynamic hashing


Static Hashing











Hashing Functions

  • Two requirements

  • mid-square (middle of square)

  • division









Hashing Functions

  • 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




Digital Analysis

  • 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




Yüklə 2,62 Mb.

Dostları ilə paylaş:
  1   2




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin