week 1 Flashcards
hash function takes as argument§
hash key
hash function has as output
bucket number
task hash key
send approx equal amount of hask keys to each of B buckets (uniformly distributed into buckets)
not good wehn B has…
common factor with most hash keys, non random distribution
choose b to be
prime
if hash key string
hash(sum(ascii_code(character in string field))) and do procedure as previously
index
data structure that makes it efficient to retrieve objects, given the value of >=1 elements of those objects
objects
= records
index is build on..
one of fields of record. given v of that field -> retrieves all records having value v in field
index implementation=
hash table
hash table
hash keys: field/fields on which indexing is done
records placed in buckets determined by hash function
given hash key -> hash it -> find bucket -> search in bucket for records with that value of hash key
disk is organized in
blocks
main memory is organized in
words
want to do computations in
main memory
blocks:
minimum uunits that OS moves to/from main memory
how much slower is it to read a disk block
it takes 10 ms, at least 5 order of magnitutes (factor of 10^5) slower than time taken to read a word (32 bits, block 64kbytes)
Define a hash-function for an index containing objects records with two fields, one of type string, and one of type integer.
hash(record(string_field, integer_field) = hash(string_field) + hash(integer_field)
hash(string_field) = hash(sum(ascii_code(character in string field)))
For both hashing the string field and hashing the integer field the following hash function is used: hash(integer) = integer mod B, where B is prime (this last condition is necessary as we do not know the range of the hash-keys).
What is a regular expression? Give examples of at least three regular expression operators.
A regular expression is a special string used to define string patterns. It uses characters and operators as “|”, “*”, “+”, etc., to denote disjunction, repetition, repetition at least one time, etc.
