计算机算法导论 第11章

计算机算法导论,第十一章

Introduction to Algorithms

III Data Structures

计算机算法导论,第十一章

Dynamic Sets

Dynamic Sets: Different from mathematical set, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. Algorithms may require several different types of operations to be performed on sets.

Dictionary: A dynamic set that only supports the ability to insert elements into, delete elements from, and test membership in a set.

计算机算法导论,第十一章

Elements of a dynamic set

Typically, each element is represented by an object.

An object = Key +satellite data

Some dynamic sets presuppose that the keys are drawn from a totally ordered set

计算机算法导论,第十一章

Operations on dynamic sets

Queries: simply return information about the set

SEARCH(S, k), returns a pointer x to an element in S such that key[x] = k, or NIL if no such element belongs to S. MINIMUM(S), returns a pointer to the element of S with the smallest key. MAXIMUM(S), returns a pointer to the element of S with the largest key. SUCCESSOR(S, x), returns a pointer to the next larger element in S, or NIL if x is the maximum element. PREDECESSOR(S, x), returns a pointer to the next smaller element in S, or NIL if x is the minimum element. INSERT(S, x), augments the set S with the element pointed to by x. DELETE(S, x), given a pointer x to an element in the set S, removes x from S.4

Modifying operations: change the set.

计算机算法导论,第十一章

Overview

The time taken to execute a set operation is usually measured in terms of the size of the set. Next few lectures will focus on data structures rather than straight algorithms1.2.

3.4. 5.

Chapter 10 presents the essentials of working with simple data structures such as stacks, queues, linked lists, and rooted trees. Chapter 11 introduces hash tables, which support the dictionary operations INSERT, DELETE, and SEARCH. Chapter 12 Binary search trees Chapter 13 Red-black trees, a variant of binary search trees Chapter 14, augment red-black trees to support operations other than the basic ones5

计算机算法导论,第十一章

11 Hash Table

计算机算法导论,第十一章

Hash Tables

Motivation: symbol tables

A compiler uses a symbol table to relate symbols to associated data

Symbols: variable names, procedure names, etc. Associated data: memory location, call graph, etc.

For a symbol table (also called a dictionary), we care about search, insertion, and deletion Typically don’t care about sorted order

计算机算法导论,第十一章

Symbol-table problem

The structure we will use is a hash table

Supports all the above in O(1) expected time!8

计算机算法导论,第十一章

Hashing: Keys

consider all keys to be (possibly large) natural numbers How can we convert floats to natural numbers for hashing purposes? How can we convert ASCII strings to natural numbers for hashing purposes?

计算机算法导论,第十一章

Review

Section 11.1 discusses direct addressing Section 11.2 presents the main ideas, focusing on "chaining" as a way to handle "collisions" Section 11.3 describes how array indices can

be computed from keys using hash functions Section 11.4 looks at "open addressing," which is another way to deal with collisions Section 11.5 introduces "perfect hashing"10

计算机算法导论,第十一章

11.1 Direct-address tables

计算机算法导论,第十一章

Direct Addressing

Suppose:

The range of keys is 0..m-1 Keys are distinct Set up an array T[0..m-1] in which

The idea:

T[i] = x if x T and key[x] = i T[i] = NULL otherwise Operations take O(1) time!

This is called a direct-address table

计算机算法导论,第十一章

Direct Addressing

计算机算法导论,第十一章

Direct Addressing

DIRECT-ADDRESS-SEARCH(T, k)return T [k]

DIRECT-ADDRESS-INSERT(T, x)T[key[x]] ← x

DIRECT-ADDRESS-DELETE(T, x)T[key[x]] ← NIL

Each of these operations is fast: only O(1) time is required.14

计算机算法导论,第十一章

The Problem With Direct Addressing

Direct addressing works well when the range m of keys is relatively small But what if the keys are 32-bit integers?

Problem 1: direct-address table will have 232 entries, more than 4 billion Problem 2: even if memory is not an issue, the time to initialize the elements to NULL may be

Solution: map keys to smaller range 0..m-1 This mapping is called a hash function15

计算机算法导论,第十一章

11.2 Hash tables

计算机算法导论,第十一章

Hash tables

计算机算法导论,第十一章

Hash tablesT

U (universe of keys)k1

0h(k1) h(k4)

k4 K (actual keys)k2

k5

h(k2) = h(k5)

k3

h(k3)m-118

计算机算法导论,第十一章

Hashing: Collisions

本文来源：https://www.bwwdw.com/article/t4oi.html