Upload
internet
View
118
Download
3
Embed Size (px)
Citation preview
Espalhamento
2
Sumário da Apresentação
Espalhamento A idéia inicial de espalhamento Métodos de EspalhamentoImplementação das funções HashImplementação do Espalhamento
Hash com encadeamento em área separada
Hash com encadeamento em área primária
Hash usando Endereçamento AbertoAplicação conta palavras (Java)
3
Sumário da Apresentação
EspalhamentoA idéia inicial de espalhamento
ExemploMétodos de Espalhamento
Método da Divisão Método do Meio do Quadrado Método da Multiplicação
Implementação das funções Hash Chaves Fundamentais Chaves de Ponto Flutuante Chaves de Cadeias de Caracteres Espalhamento de Objetos Espalhamento de Containers Associações
4
Sumário da Apresentação
Hash com encadeamento em área separada Tabelas Hash Abstratas (só Java) Encadeamento Separado
Implementação Construtor e Destrutor (C++) Construtor e métodos getLength e purge (Java) Inserção e exclusão de itens Encontro de itens
Hash com encadeamento em área primária Tabelas de Espalhamento Encadeadas
Implementação Construtor e Destrutor (C++) Construtor e métodos getLength e purge (Java) Inserção e encontro de itens Exclusão de itens
5
Sumário da Apresentação
Hash usando Endereçamento Aberto Sondagem linear Sondagem Quadrática Duplo Hashing Implementação
Construtor e Destrutor Inserção de itens Encontro de itens Exclusão de itens
Espalhamento
7
Sumário do item Espalhamento
A idéia inicial de espalhamentoExemplo
Métodos de EspalhamentoMétodo da DivisãoMétodo do Meio do QuadradoMétodo da Multiplicação
8
A idéia inicial de espalhamento
Exemplo:Deseja-se implementar um container de busca que será
usado paraarmazenar cadeias de caracteres, K
K = {“ett”; “tva”, “tre”, “fyra”; “fem”; “sex”²; “aju”, “atta”; “nio”; “tio”; “elva”; “tolv”}.
Considere-se a definição de uma função de espalhamento,ou “hash”, como mostrado na figura abaixo:
x h(x) x h(x)"ett" 1 "sju“ 7"två" 2 "åtta“ 8"tre“ 3 "nio“ 9 "fyra“ 4 "tio“ 10 "fem" 5 "elva“ 11"sex“ 6 "tolv“ 12
9
Espalhamento em memória Secundária
O Espalhamento em memória secundária é o processo preferencial para a implantação dos arquivos de acesso direto.
10
Espalhamento em Memória Secundária
1- Agrupar um determinado número de registros em uma unidade com endereço comum chamada "bucket".
2- Calcular o espaço de armazenamento necessário para o arquivo. Esse dimensionamento do arquivo depende da densidade de empacotamento ou fator de carga que é a razão entre o número de registros nos arquivos e a capacidade total dos "buckets".
3- Escolher uma função "hash" que é a transformação a aplicar à chave para obter o endereço do "bucket".
4- Optar por uma técnica de resolução do problema de transbordamento. Ocorre transbordamento ou "overflow" quando se endereça um registro a um "bucket" já cheio.
11
Buckets (1)
O arquivo é dividido em seções menores denominadas "buckets", que podem conter um ou mais registros. A função "Hash" atribui a cada registro um endereço de "bucket" ("home address"), onde este pode ser acomodado.O tamanho de “bucket” é determinado pelo número de registros que este pode armazenar, ou ainda, pelo número de "slots" que ele contém. Um "slot" é uma unidade de armazenamento que contém espaço para um registro.Um arquivo com 1000 registros pode ser composto de 1.000 "buckets" de tamanho 1, ou 500 "buckets" de tamanho 2, etc...Pode-se relacionar o tamanho do "bucket" a características físicas do meio de armazenamento. Logo, o tempo de transporte do “bucket” para a memória principal é proporcional ao tamanho do bucket.
12
Buckets (2)
Ocorre uma colisão quando durante uma inclusão de registros, dois deles têm o mesmo endereço calculado pela função “hash”. Estes registros são chamados sinônimos. As colisões não constituem problemas enquanto não se atingir a capacidade do "bucket" correspondente. A partir daí, ocorre transbordamento, que consiste no fato de um registro não poder ser acomodado em "home bucket". Define-se como "home bucket" aquele que está associado ao "home address" do registro, que fora calculado pela função "hash" aplicada à chave do registro.Aumentando o tamanho dos "buckets" diminui a probabilidade de transbordamento mas aumenta o tempo de busca do registro no "bucket". Contudo, o acesso à memória principal é mais rápido comparado com o tempo de busca em memória secundária, uma vez que o “bucket” será transferido para memória principal.
Métodos de Espalhamento
14
Método do resto da Divisão
Para este caso a função hash é h(x) = x mod M, sendo M o número de endereços disponíveis para armazenamento.Pode-se implementar um container de busca usando um array de tamanho n=12. Para inserir o item x, basta armazena-lo na posição h(x)-1 do array.Os elementos do conjunto K são chamados de chaves.É usual armazenar estas chaves em um array ou arquivo.Imediatamente pode-se utilizar esta idéia para armazenar não apenas cadeias de caracteres e sim objetos dos quais um dos atributos seja uma chave do conjunto K.A técnica de "hashing" proporciona uma recuperação de registros extremamente rápida se comparada com a recuperação seqüencial. O tempo de recuperação em arquivos sequenciais cresce com o tamanho do arquivo, o que não ocorre com o "hashing". No projeto de um arquivo de acesso direto os fatores que é necessário considerar são os seguintes:
15
Método do Meio Quadrado
O espalhamento pelo meio do quadrado considera que M = 2k, o número de endereços (“buckets”), é um múltiplo de 2. Para palavras de tamanho W, com w bits as operações inteiras são feitas módulo W.A função é hash de x é obtida elevando x ao quadrado módulo W e reduzindo este número ao domínio {0,1,...,M-1} por meio da multiplicação por dois elevado a w-k o que zera os w-k bits à esquerda.
O código que se segue mostra esta implementação
unsigned int const k = 10; // M==1024unsigned int const w = bitsizeof(unsigned int);
unsigned int h(unsigned int x) { return (x * x) >> (w - k);}
16
Método da Multiplicação
Uma variação do método do meio do quadrado é o método da multiplicação, pelo qual hash de x não multiplica x por si mesmo e sim por uma constante a
A escolha de a deve ser tal que seja relativamente primo com W, o que se consegue achando a' tal que aa’ = 1 (mod W). Ou seja, a' é a inversa de a modulo W.Vale a propriedade axa'=aa'x=1x. Para palavras de 32 bits pode-se escolher a = 2.654.435.769 cuja representação binária é
10 011 110 001 101 110 111 100 110 111 001.Sua inversa é O código que se segue mostra esta implementação
unsigned int const k = 10; // M==1024unsigned int const w = bitsizeof(unsigned
int);unsigned int const a = 2654435769U;unsigned int h(unsigned int x);
Implementação das funções Hash
18
Sumário do itemImplementação das funções Hash
Chaves InteirasChaves de Ponto FlutuanteChaves de Cadeias de CaracteresEspalhamento de ObjetosEspalhamento de ContainersAssociações
19
Fundamentos
As chaves dos objetos podem ser de quaisquer tipos de dados até estruturas como associações ou containers.Para um conjunto de chaves, K, e uma constante positiva M, uma função hash é da forma h: K {0,1,..., M-1}É conveniente implementar a função h como uma composição de duas funções f e g. A função f mapeia chaves em inteiros f: K Z+
aonde Z+ é o conjunto dos inteiros não negativos. A função g mapeia inteiros não negativos em {0, 1, ..., M-1}, g: Z+ {0, 1, ..., M-1}
Desde que sejam conhecidas as funções f e g, a função hash h é definida como a composição delas: h = f g
Ou seja, o valor de hash de uma chave x é dado por g(f(x)).
Implementação das funções Hash
Implementação C++
21
Chaves Inteiras
A função f que mapeia chaves em inteiros para chaves constituídas de inteiros é f(x) = x
Definição da Função Hash de Inteiros
// pgm08_01.cpp
typedef unsigned int HashValue;
HashValue Hash (char c) { return abs (c); }
HashValue Hash (int i) { return abs (i); }
22
Chaves de Ponto FlutuanteTodo real não nulo x pode ser expresso da forma x = m * 2e , sendo A função f pode ser escrita
Sendo W o maior inteiro que pode ser expresso em uma palavra do computador x e y colidirão se suas mantissas diferirem de menos de 1/2W independente do valor dos expoentes. Definição da Função Floating-Point Hash
// pgm08_02.cppHashValue Hash (double d) {
if (d == 0)return 0;
else {int exponent;double mantissa = std::frexp (d, &exponent);return (2 * fabs (mantissa) - 1) * ~0U;
}}
23
Chaves de Cadeias de Caracteres
Para chaves constituídas de cadeias de caracteres pode-se concatenar as representações dos caracteres. Sendo, por exemplo strings de comprimento 4 , estes strings podem ser transformados em inteiros pela expressão Sendo potência de 2 pode-se escrever a função C++:
HashValue Hash (string const& s)
{ return s[0] << 24 | s[1] << 16 | s[2] << 8 | s [3]; }
Para tratar strings de comprimento n pode-se fazer
O inconveniente é que não se está fixando limites para f(s). Pode-se corrigir isto fazendo
aonde
24
Chaves de Cadeias de Caracteres
Sendo W e B potencias de dois o valor calculado depende apenas dos últimos W/B caracteres do string.Para e , todos os strings que possuam os mesmos quatro caracteres colidem.Considerando f(s) como um polinômio em B, os coeficientes do polinômio, si, podem ser calculados pela Regra de Horner, que evita o cálculo dos expoentes de x.
HashValue result = 0;
for (unsigned int i = 0; s [i] != 0; ++i) result = result * B + s [i];
Como o efeito de consideração de polinômio de base 2 é semelhante ao deslocamento (shift) basta concatenar os resultados parciais
25
Chaves de Cadeias de Caracteres
HashValue result = 0;for (unsigned int i = 0; s [i] != 0; ++i) result = result << b ^ s [i];
Pode-se estudar os efeitos de consideração dos caracteres mais à esquerda e mais à direita ou ainda utilizar a regra do polinômio com coeficientes variáveis, por exemplo, obtidos de um array s.
Definição da Função Hash de Character String
//pgm08_03.cpp
unsigned int const shift = 6;HashValue const mask = ~0U << (bitsizeof (HashValue) - shift);HashValue Hash (std::string const& s){ HashValue result = 0; for (unsigned int i = 0; s [i] != 0; ++i)
result = (result & mask) ^ (result << shift) ^ s [i]; return result;}
26
Espalhamento de ObjetosUm template da classe Wrapper é usado para envelopar instâncias de tipos de dados C++ construídos em uma interface abstrata Object. Usando o template as quatro classes Char, Int, Double, and String são declaradas da forma:
typedef Wrapper<char> Char;typedef Wrapper<int> Int;typedef Wrapper<double> Double;typedef Wrapper<string> String;
Como estas classes devem ser concretas devem ter implementações de todas as funções membros, inclusive a função Hash.
Definição da função Menbro Hash da Classe Wrapper<T>
//pgm08_04.cpp template <class T>HashValue Wrapper<T>::Hash () const { return ::Hash (datum); }
27
Espalhamento de Containers
A função hash f(c) de um container c, com n objetos, o1, o2, …, on é definida como
Para obter o hash de um container calcula-se a soma dos valores hash dos objetos contidos.A função Container::Hash usa a função Accept para fazer um visitante especial HashingVisitor visitar todos os objetos do container. Quando visita um objeto chama a função Hash do visitado e acumula o resultado.Definição da função Membro Hash da Classe Container
28
Espalhamento de Containers
// pgm08_05.cpp
class HashingVisitor : public Visitor { HashValue value;public: HashingVisitor (HashValue _value) : value (_value) {} void Visit (Object& object)
{ value += object.Hash (); } HashValue Value () const
{ return value; }};
HashValue Container::Hash () const { HashingVisitor visitor (::Hash (typeid (*this).name())); Accept (visitor); return visitor.Value ();}
29
Associações
Já que a função Accept é virtual todas as classes derivadas da classe Container fornecerão as implementações correspondentes.Utilizando o conceito de chave pode-se escrever A = {(k,v):kK, v V}A função hash pode ser expressa como fAA(k,v) = fK(k)Sedo fk a função hash associada ao conjunto K. Uma Association possui dois objetos
class Association : public Object, public Ownership {Object* key;Object* value;...};Para definir a função hash de uma associação basta chamar a função membro hash do objeto para o qual a variável membro key apontaDefinição da Função Hash Member da classe Association
HshValue Association::Hash() const{ return key->Hash(): }
Implementação das funções Hash
Implementação Java
31
Método hashCode da classe Int
A função f que mapeia chaves em inteiros para chaves constituídas de inteiros é f(x) = x
// pgm08_01.java
public class Int extends AbstractObject{
protected int value;public int hashCode(){
return value;}// ...
}
32
Método hashCode da classe Dbl
A definição da função f é:
// pgm08_02.java
public class Dbl extends AbstractObject
{
protected double value;
public int hashCode()
{
long bits = Double.doubleToLongBits(value);
return (int)(bits >>> 20);
}
// ...
}
33
Chaves de Cadeias de Caracteres
Para chaves constituídas de cadeias de caracteres pode-se concatenar as representações dos caracteres. Sendo, por exemplo strings de comprimento 4 , este string pode ser transformado em inteiro pela expressão Sendo B=27 potência de 2 pode-se escrever a função Java:
static int f (String s)
{ return s.charAt(0) << 21 | s.charAt (1) << 14 |
s.charAt (2) << 7 | s.charAt (3); }
Para tratar strings de comprimento n pode-se fazer
O inconveniente é que não se está fixando limites para f(s). Pode-se corrigir isto fazendo
aonde
34
Chaves de Cadeias de Caracteres
Sendo W e B are potencias de dois o valor calculado depende apenas dos últimos W/B caracteres do string.Para e , todos os strings que possuam os mesmos quatro caracteres colidem.Considerando f(s) como um polinômio em B, os coeficientes do polinômio, si, podem ser calculados pela Regra de Horner, que evita o cálculo dos expoentes de x.
static int f (String s) { int result = 0; for (int i = 0; i < s.length (); ++i) result = result * B + s.charAt (i); return result; }
Como o efeito de consideração de polinômio de base 2 é semelhante ao deslocamento (shift) basta concatenar os resultados parciais
35
Chaves de Cadeias de Caracteres
static int f (String s) { int result = 0; for (int i = 0; i < s.length () ; ++i) result = result << b ^ s.charAt (i); return result; }
Pode-se estudar os efeitos de consideração dos caracteres mais à esquerda e mais à direita ou ainda utilizar a regra do polinômio com coeficientes variáveis, por exemplo, obtidos de um array s.
36
Método hashCode da classe Str
// pgm08_03.java
public class Str extends AbstractObject{
protected String value;private static final int shift = 6;private static final int mask = ~0 << (32 - shift); public int hashCode(){
int result = 0;for(int i = 0; i < value.length (); ++i)
result = (result & mask) ^ (result << shift) ^ value.charAt (i);
return result;}// ...
}
37
Espalhamento de Containers
A função hash f(c) de um container c, com n objetos, o1, o2, …, on é definida como
Para obter o hash de um container calcula-se a soma dos valores hash dos objetos contidos.
38
Método hashCode da classe AbstractContainer
// pgm08_04.java
public abstract class AbstractContainerextends AbstractObject implements Container {protected int count;public int hashCode() {
Visitor visitor = new AbstractVisitor() { private int value;
public void visit (Object object) { value += object.hashCode();
} public int hashCode() {
return value; }};accept (visitor);return getClass().hashCode() + visitor.hashCode
();}// ...
}
39
Associações
Já que a função Accept é virtual todas as classes derivadas da classe Container fornecerão as implementações correspondentes.Utilizando o conceito de chave pode-se escrever
A função hash pode ser expressa como
Sedo fk a função hash associada ao conjunto K. Uma Association possui dois objetos
public class Association extends AbstractObject {
protected Comparable key; protected Object value;...};Para definir a função hash de uma associação basta chamar a função membro hash do objeto para o qual a variável key membro aponta
40
Método hashCode da classe Association
// pgm08_05.java
public class Association extends AbstractObject
{
protected Comparable key;
protected Object value;
public int hashCode()
{
return key.hashCode();
}
// ...
}
Implementação do Espalhamento
42
Sumário do item Implantação do Espalhamento
Hash com encadeamento em área separada Tabelas Hash Abstratas (só Java) Encadeamento Separado
Hash com encadeamento em área primária Tabelas de Espalhamento Encadeadas
Hash usando Endereçamento Aberto Sondagem linear Sondagem Quadrática Duplo Hashing Implementação
Implementação do Espalhamento
Implementação C++
44
Tabelas Hash
Definição da Classe HashTable
//pgm08_07.cppclass HashTable : public virtual SearchableContainer {protected: unsigned int length;public: HashTable (unsigned int); virtual unsigned int H (Object const&) const;};
Implementação do EspalhamentoC++
Hash com encadeamento em área separada
46
Tabelas Hash
Definição das funções H Member e do Constructor da Classe HashTable
//pgm08_08.cpp
HashTable::HashTable (unsigned int _length) :
length (_length)
{}
unsigned int HashTable::H (Object const& object) const
{ return object.Hash () % length; }
O construtor de HashTable recebe um simples argumento e inicializa a variável membro de maneira adequada. A função membro corresponde à composição h = g f. A função membro H recebe como argumento uma referencia constante a um objeto e retorna o resultado Hash modulo length.
47
Encadeamento Separado
Tabela Hash usando Encadeamento Separado
48
Definição da Classe ChainedHashTable
// pgm08_09.cpp
class ChainedHashTable : public HashTable{ Array<LinkedList<Object*> > array;public: ChainedHashTable (unsigned int); // ...};
49
Definição das funções Purge Member, Constructor e Destructor da Classe ChainedHashTable (1)
// pgm08_10.cpp
ChainedHashTable::ChainedHashTable (unsigned int _length) :
HashTable (_length),
array (_length)
{}
50
Definição das funções Purge Member, Constructor e Destructor da Classe ChainedHashTable (2)
// pgm08_10.cpp (Continuação)
void ChainedHashTable::Purge(){ for (unsigned int i = 0; i < length; ++i) {
if(IsOwner ()) { ListElement<Object*> const* ptr; for( ptr = array[i].Head (); ptr != 0;
ptr = ptr->Next() ) delete ptr->Datum ();
}array[i].Purge();
} count = 0;}
ChainedHashTable::~ChainedHashTable () { Purge (); }
51
Definição das Funções Insert e Withdraw Member da Classe ChainedHashTable
// pgm08_11.cpp
void ChainedHashTable::Insert (Object& object){ array [H (object)].Append (&object); ++count;}
void ChainedHashTable::Withdraw (Object& object){ array [H (object)].Extract (&object); --count;}
52
Definição da Função Find Member da Classe ChainedHashTable
// pgm08_12.cpp
Object& ChainedHashTable::Find (Object const& object) const{ ListElement<Object*> const* ptr; for(ptr = array [H (object)].Head (); ptr != 0;
ptr = ptr->Next()) {
if(object == *ptr->Datum ()) return *ptr->Datum ();
} return NullObject::Instance ();}
Implementação do EspalhamentoC++
Hash com encadeamento em área primária
54
Hash com encadeamento em área primária
Quando é usado Hash com encadeamento em área primária o transbordamento é tratado por listas encadeadas iniciadas nos “home addresses”.
55
Definição da Classe ChainedScatterTable
// pgm08_13.cpp
class ChainedScatterTable : public HashTable{ class Entry { public:
enum { null = ~0U };Object* object;unsigned int next;
Entry (); };
Array<Entry> array;public: ChainedScatterTable (unsigned int); // ...};
56
Definição das Funções Purge Member, Constructor e Destructor da Classe ChainedScatterTable e Constructor da Classe ChainedScatterTable::Entry (1)
//pgm08_14.cpp
ChainedScatterTable::Entry::Entry () : object (0), next (null) {}
ChainedScatterTable::ChainedScatterTable (unsigned int _length) :
HashTable (_length), array (_length) {}
57
Definição das Funções Purge Member, Constructor e Destructor da Classe ChainedScatterTable e Constructor da Classe ChainedScatterTable::Entry (2)
// pgm08_14.cpp (Continuação)
void ChainedScatterTable::Purge (){ for(unsigned int i = 0; i < length; ++i) {
if(array [i].object != 0) { if(IsOwner ()) delete array [i].object; array [i] = Entry ();
} }
count = 0;}ChainedScatterTable::~ChainedScatterTable () { Purge (); }
58
Definição das Funções Insert e Find Member da Classe ChainedScatterTable (1)
// pgm08_15.cpp
void ChainedScatterTable::Insert (Object& object) { if (count == length)
throw domain_error ("scatter table is full"); unsigned int probe = H(object); if(array[probe].object != 0) {
while(array[probe].next != Entry::null) probe = array [probe].next;
unsigned int const tail = probe;probe = (probe + 1) % length;while(array[probe].object != 0)
probe = (probe + 1) % length;array[tail].next = probe;
}
59
Definição das Funções Insert e Find Member da Classe ChainedScatterTable (2)
// pgm08_15.cpp (Continuação)
array[probe].object = &object; array[probe].next = Entry::null; ++count;}
Object& ChainedScatterTable::Find(Object const& object)const
{ for(unsigned int probe = H (object);
probe != Entry::null; probe = array [probe].next) {
if(object == *array[probe].object)return *array[probe].object;
} return NullObject::Instance();}
60
Definição da Função Withdraw Member da Classe ChainedScatterTable (1)
// pgm08_16.cpp
void ChainedScatterTable::Withdraw (Object& object)
{
if(count == 0)
throw domain_error ("scatter table is empty");
unsigned int i = H (object);
while(i != Entry::null && array[i].object != &object)
i = array[i].next;
if(i == Entry::null)
throw invalid_argument ("object not found");
61
// pgm08_16.cpp (Continuação)
for(;;) { unsigned int j; for(j = array[i].next; j != Entry::null; j =
array[j].next) {
unsigned int const h = H (*array[j].object); bool contained = false; for(unsigned int k = array[i].next; k !=
array[j].next && !contained; k = array[k].next) { if(k == h)
contained = true; } if(!contained)
break; }
Definição da Função Withdraw Member da Classe ChainedScatterTable (2)
62
Definição da Função Withdraw Member da Classe ChainedScatterTable (3)
// pgm08_16.cpp (Continuação)
if(j == Entry::null) break; array[i].object = array[j].object;
i = j; } array[i].object = 0; array[i].next = Entry::null; for(unsigned int j = (i + length - 1U) % length; j != i;
j = (j + length - 1U) % length) { if(array[j].next == i) {
array[j].next = Entry::null; break;
} } --count;}
Implementação do EspalhamentoC++
Hash usando Endereçamento Aberto
64
Tabelas de Espalhamento usando Endereçamento Aberto (1)
A seqüência de sondagem é uma seqüência de funções
aonde hi é uma função hash hi: K {0,1,...,M-1} A inserção de um item x na tabela de espalhamento é feita
examinando as posições h0(x), h1(x),..., até encontrar uma célula vazia.
A busca de um item na tabela segue a mesma seqüência.As seqüências de sondagem mais comuns são do tipo
para i = 0,1,…,M-1
A função c(i) representa a estratégia de resolução de transbordamentos.
110 ,...,, Mhhh
ii Micxhxh mod))()(()(
65
Tabelas de Espalhamento usando Endereçamento Aberto (2)
Sondagem Linear
Na sondagem linear a função c(i) é linear em i.
Ou, da maneira mais comum
e M devem ser primos relativos.
Para i = 0,1,…,M-1
)()( iic
)()( iic
Mixhhi mod))((
66
Tabelas de Espalhamento usando Endereçamento Aberto (3)
Tabela de Espalhamento usando Endereçamento Aberto e Sondagem Linear
67
Tabelas de Espalhamento usando Endereçamento Aberto (4)
Sondagem Quadrática
Na sondagem linear a função c(i) é quadrática em i.
Ou, da maneira mais comum
iiic 2)(
2)( iic
68
Tabelas de Espalhamento usando Endereçamento Aberto (5)
Duplo Hashing
Pode-se gerar uma seqüência de sondagem por meio da técnica de duplo hashing que usa duas funções h e h’ .
A seqüência de sondagem é obtida da forma
1,...,1,0: MKh
1,...,2,1:' MKh
Mxihxhxhi mod))()(()( '
69
Definição da Classe OpenScatterTable// pgm08_17.cpp
class OpenScatterTable : public HashTable { class Entry {
public:enum State { empty, occupied, deleted };State state;Object* object;Entry ();
}; Array<Entry> array; unsigned int C (unsigned int) const; unsigned int FindMatch (Object const&) const; unsigned int FindInstance (Object const&) const; unsigned int FindUnoccupied (Object const&) const;public: OpenScatterTable (unsigned int); // ...};
70
Construtores e Destrutores
O construtor default para a classe OpenScatterTable::Entry faz com que uma entrada não ocupada tenha o ponteiro para seu objeto zerada e o estado default de todas as entradas é empty. Este construtor default inicializa as duas variáveis membro de maneira adequada.
71
Definição do Constructor e Destructor da Classe OpenScatterTable e do Constructor da Classe OpenScatterTable::Entry// pgm08_18.cpp
OpenScatterTable::Entry::Entry() : state (empty), object (0) {}
OpenScatterTable::OpenScatterTable (unsigned int _length) :
HashTable (_length), array (_length) {}
void OpenScatterTable::Purge() { for (unsigned int i = 0; i < length; ++i) {
if (array [i].state == Entry::occupied) { if (IsOwner ())
delete array [i].object; array [i] = Entry ();
} } count = 0;}OpenScatterTable::~OpenScatterTable () { Purge (); }
72
Definição das Funções C, FindUnoccupied e Insert Member da Classe OpenScatterTable (1)
// pgm08_19.cpp
unsigned int OpenScatterTable::C (unsigned int i) const { return i; }
unsigned int OpenScatterTable::FindUnoccupied(Object const& object) const
{ unsigned int const hash = H (object); for (unsigned int i = 0; i < count + 1; ++i) {
unsigned int const probe = (hash + C (i)) % length;
if (array [probe].state != Entry::occupied) return probe;
} return length;}
73
Definição das Funções C, FindUnoccupied e Insert Member da Classe OpenScatterTable (2)
// pgm08_19.cpp
void OpenScatterTable::Insert(Object& object) { if (count == length)
throw domain_error ("scatter table is full"); unsigned int const offset = FindUnoccupied
(object); array [offset].state = Entry::occupied; array [offset].object = &object; ++count;}
A função c define a seqüência de sondagem. Para sondagem linear a função c é a função identidade.
A função membro FindUnoccupied é encontrar uma posição desocupada. A rotina FindUnoccupied sonda o array de acorde com a seqüência de sondagem determinada pela função c.
74
Definição das Funções FindMatch e Find Member da Classe OpenScatterTable (1)
// pgm08_20.cpp
unsigned int OpenScatterTable::FindMatch(Object const& object) const
{ unsigned int const hash = H (object); for(unsigned int i = 0; i < length; ++i)
{unsigned int const probe = (hash + C (i)) %
length;if(array[probe].state == Entry::empty)
break;if(array[probe].state == Entry::occupied && object == *array[probe].object)
return probe; } return length;}
75
Definição das Funções FindMatch e Find Member da Classe OpenScatterTable (2)
// pgm08_20.cpp (Continuação)
Object& OpenScatterTable::Find (Object const& object) const
{ unsigned int const offset = FindMatch (object); if (offset < length)
return *array [offset].object; else
return NullObject::Instance ();}
76
Definição da Função Withdraw Member da Classe OpenScatterTable
// pgm08_21.cpp
void OpenScatterTable::Withdraw (Object& object){ if (count == 0)
throw domain_error ("scatter table is empty"); unsigned int const offset = FindInstance (object); if (offset == length)
throw invalid_argument ("object not found"); array [offset].state = Entry::deleted; array [offset].object = 0; --count;}
77
OpenScatterTable Class Alternate Withdraw Member Function (1)// pgm08_22.cpp
void OpenScatterTable::Withdraw(Object& object){ if(count == 0)
throw domain_error ("scatter table is empty"); unsigned int i = FindInstance (object); if(i == length)
throw invalid_argument ("object not found"); for(;;) {
unsigned int j; for(j = (i + 1) % length; array[j].state ==
Entry::occupied; j = (j + 1) % length) { unsigned int const h = H (*array [j].object); if( (h <= i && i < j) || (i < j && j < h) ||
(j < h && h <= i) ) break;
}
78
OpenScatterTable Class Alternate Withdraw Member Function (2)
// pgm08_22.cpp (Continuação)
if(array[j].state == Entry::empty)
break;
array[i] = array[j];
i = j;
}
array[i].state = Entry::empty;
array[i].object = 0;
--count;
}
Implementação Java
Implementação do EspalhamentoJava
Hash com encadeamento em área separada
81
Tabelas Hash
Interface HashTable// pgm08_06.java
public interface HashTable extends SearchableContainer
{
double getLoadFactor();
}
82
Métodos AbstractHashTable
// pgm08_07.java
public abstract class AbstractHashTableextends AbstractSearchableContainer implements HashTable
{public abstract int getLength();
protected final int f(Object object) {return object.hashCode();
}protected final int g(int x) {
return Math.abs(x) % getLength();}protected final int h(Object object) {
return g( f(object) );}// ...
}
83
Encadeamento Separado
Tabela Hash usando Encadeamento Separado
84
Campos ChainedHashTable
// pgm08_08.java
public class ChainedHashTable extends AbstractHashTable
{
protected LinkedList[] array;
// ...
}
85
Métodos constructor, getLength e purge da classe ChainedHashTable
// pgm08_09.java
public class ChainedHashTable extends AbstractHashTable {protected LinkedList[] array;public ChainedHashTable(int length) {
array = new LinkedList [length];for(int i = 0; i < length; ++i) array[i] = new LinkedList();
}public int getLength() {
return array.length;}public void purge() {
for(int i = 0; i < getLength(); ++i)array[i].purge();count = 0;
}// ...
}
86
Métodos insert e withdraw da classe ChainedHashTable
// pgm08_10.java
public class ChainedHashTable extends AbstractHashTable{
protected LinkedList[] array;public void insert(Comparable object){
array[h (object)].append(object);++count;
}public void withdraw(Comparable object){
array[h (object)].extract(object);--count;
}// ...
}
87
Método find da classe ChainedHashTable
// pgm08_11.java
public class ChainedHashTable extends AbstractHashTable{
protected LinkedList[] array;public Comparable find(Comparable object){
for(LinkedList.Element ptr = array[h(object)].getHead(); ptr != null; ptr = ptr.getNext()){
Comparable datum = (Comparable) ptr.getDatum();if(object.isEQ (datum))
return datum;}return null;
}// ...
}
88
Método getLoadFactor da classe AbstractHashTable
// pgm08_12.java
public abstract class AbstractHashTable
extends AbstractSearchableContainer implements HashTable
{
public abstract int getLength();
public final double getLoadFactor()
{
return (double) getCount() / getLength();
}
// ...
}
Implementação do EspalhamentoJava
Hash com encadeamento em área primária
90
•Quando é usado Hash com encadeamento em área primária o transbordamento é tratado por listas encadeadas iniciadas nos “home addresses”.
Hash com encadeamento em área primária
91
Classe ChainedScatterTable.Entry e campos ChainedScatterTable
// pgm08_13.java
public class ChainedScatterTable extends AbstractHashTable{
protected Entry[] array;static final int nil = -1;protected static final class Entry {
Comparable object;int next = nil;void purge() { object = null; next = nil;}
}// ...
}
92
Métodos constructor, getLength e purge da classe ChainedScatterTable (1)
// pgm08_14.java
public class ChainedScatterTableextends AbstractHashTable
{protected Entry[] array;
public ChainedScatterTable(int length){
array = new Entry [length];for(int i = 0; i < length; ++i) array [i] = new Entry ();
}
93
Métodos constructor, getLength e purge da classe ChainedScatterTable (2)
// pgm08_14.java (Continuação)
public int getLength(){ return array.length;}
public void purge(){ for(int i = 0; i < getLength (); ++i)
array [i].purge(); count = 0;
}// ...
}
94
Métodos insert e find da classe ChainedScatterTable (1)
// pgm08_15.java
public class ChainedScatterTable extends AbstractHashTable{
protected Entry[] array;public void insert(Comparable object) {
if(count == getLength ()) throw new ContainerFullException();int probe = h(object);if(array[probe].object != null) { while(array[probe].next != nil)
probe = array [probe].next; int tail = probe; probe = (probe + 1) % getLength(); while(array[probe].object != null)
probe = (probe + 1) % getLength(); array[tail].next = probe;}
95
// pgm08_15.java (Continuação)
array[probe].object = object;array[probe].next = nil;++count;
}public Comparable find(Comparable object) {
for(int probe = h(object); probe != nil; probe = array [probe].next) {
if( object.isEQ(array[probe].object) ) return array[probe].object;}return null;
}// ...
}
Métodos insert e find da classe ChainedScatterTable (2)
96
Método withdraw da classe ChainedScatterTable (1)
// pgm08_16.java
public class ChainedScatterTable extends AbstractHashTable{
protected Entry[] array;
public void withdraw(Comparable object){
if(count == 0) throw new ContainerEmptyException();int i = h(object);while(i != nil && object != array[i].object) i = array[i].next;if(i == nil) throw new IllegalArgumentException("obj not
found");
97
// pgm08_16.java (Continuação)
for(;;){ int j = array[i].next; while(j != nil) { int h = h(array[j].object);
boolean contained = false; for(int k = array[i].next; k != array[j].next
&& !contained; k = array[k].next) {
if(k == h) contained = true;
}
Método withdraw da classe ChainedScatterTable (2)
98
Método withdraw da classe ChainedScatterTable (3)
// pgm08_16.java (Continuação)
if(!contained) break; j = array[j].next;
} if(j == nil)
break; array[i].object = array[j].object; i = j;}
99
// pgm08_16.java (Continuação)
array[i].object = null;array[i].next = nil;for(int j = (i + getLength () - 1) % getLength (); j != i; j = (j + getLength () - 1) % getLength
()){ if(array[j].next == i) {
array[j].next = nil; break;
}}--count;
}// ...
}
Método withdraw da classe ChainedScatterTable (3)
Implementação do EspalhamentoJava
Hash usando Endereçamento Aberto
101
Hash usando endereçamento aberto
•Tabela de Espalhamento usando Endereçamento Aberto e Sondagem Linear
102
OpenScatterTable.Entry e campos OpenScatterTable fields
// pgm08_17.java
public class OpenScatterTable extends AbstractHashTable {protected Entry[] array;static final int empty = 0;static final int occupied = 1;static final int deleted = 2;protected static final class Entry {
int state = empty;Comparable object;void purge() { state = empty; object = null;}
}// ...
}
103
Métodos constructor, getLength e purge da classe OpenScatterTable
// pgm08_18.java
public class OpenScatterTable extends AbstractHashTable {protected Entry[] array;public OpenScatterTable(int length) {
array = new Entry [length];for(int i = 0; i < length; ++i) array[i] = new Entry();}public int getLength() { return array.length;}public void purge() {for (int i = 0; i < getLength (); ++i) array[i].purge();count = 0;
}// ...
}
104
Métodos c, findUnoccupied e insert da classe OpenScatterTable (1)
// pgm08_19.java
public class OpenScatterTable extends AbstractHashTable {
protected Entry[] array;protected static int c(int i) {
return i;}protected int findUnoccupied(Object object) {
int hash = h(object);for(int i = 0; i < count + 1; ++i) { int probe = (hash + c (i)) % getLength(); if(array [probe].state != occupied)
return probe;}throw new ContainerFullException();
}
105
// pgm08_19.java (Continuação)
public void insert(Comparable object){
if(count == getLength ()) throw new ContainerFullException();int offset = findUnoccupied(object);array[offset].state = occupied;array[offset].object = object;++count;
}// ...
}
Métodos c, findUnoccupied e insert da classe OpenScatterTable (2)
106
Métodos findMatch e find da classe OpenScatterTable (1)
//pgm08_20.java
public class OpenScatterTable extends AbstractHashTable{
protected Entry[] array;protected int findMatch(Comparable object) {
int hash = h(object);for(int i = 0; i < getLength (); ++i) { int probe = (hash + c (i)) % getLength(); if(array[probe].state == empty)
break; if(array[probe].state == occupied &&
object.isEQ(array[probe].object)) { return probe;
}}return -1;
}
107
// pgm08_20.java (Continuação)
public Comparable find(Comparable object) {
int offset = findMatch(object);if(offset >= 0) return array[offset].object;else return null;
}// ...
}
Métodos findMatch e find da classe OpenScatterTable (2)
108
Método withdraw da classe OpenScatterTable
//pgm08_21.java
public class OpenScatterTable extends AbstractHashTable {protected Entry[] array;public void withdraw(Comparable object) {
if(count == 0) throw new ContainerEmptyException();int offset = findInstance(object);if(offset < 0) throw new IllegalArgumentException("object not
found");array[offset].state = deleted;array[offset].object = null;--count;
}// ...
}
109
Método OpenScatterTableV2 withdraw (1)
// pgm08_22.java
public class OpenScatterTableV2 extends OpenScatterTable {public void withdraw(Comparable object) {
if(count == 0) throw new ContainerEmptyException();int i = findInstance(object);if(i < 0) throw new IllegalArgumentException("object not found");for(;;) { int j = (i + 1) % getLength(); while(array[j].state == occupied) {
int h = h(array[j].object);if((h <= i && i < j) || (i < j && j < h) || (j < h && h <= i)) break;j = (j + 1) % getLength();
}
110
// pgm08_22.java (Continuação)
if(array[j].state == empty)break;
array[i].state = array[j].state; array[i].object = array[j].object; i = j;}array[i].state = empty;array[i].object = null;--count;
}// ...
}
Método OpenScatterTableV2 withdraw (2)
Aplicação
Java
112
Aplicação Hash/scatter table –contador de palavras (1)
// pgm08_23.java
public class Algorithms{
private static final class Counter extends Int{
Counter(int value){ super(value);}void increment(){ ++value;}
}
113
Aplicação Hash/scatter table –contador de palavras (2)
// pgm08_23.java (Continuação)
public static void wordCounter(Reader in, PrintWriter out) throws IOException
{HashTable table = new ChainedHashTable(1031);StreamTokenizer tin = new StreamTokenizer(in);while(tin.nextToken() != StreamTokenizer.TT_EOF){ String word = tin.sval; Object obj = table.find(new
Association(new Str (word))); if(obj == null) table.insert(new Association(new Str(word),
new Counter(1)));
114
Aplicação Hash/scatter table –contador de palavras (3)
// pgm08_23.java (Continuação)
else { Association assoc = (Association) obj; Counter counter = (Counter)
assoc.getValue(); counter.increment(); }}out.println(table);
}}
115
Aplicações
Aplicação da Hash/Scatter Table--Contando Palavras
Uma aplicação de espalhamento é a contagem do número de ocorrências distintas de cada palavra contida em um arquivo texto.
AplicaçõesAplicação da Hash/Scatter Table--Contando Palavras (1)
//pgm08_23.cpp
class Counter : public Int {public: Counter (int i) : Int(i) {} void operator ++ ()
{ ++datum; }};
116
Aplicações
AplicaçõesAplicação da Hash/Scatter Table--Contando Palavras (2)
// pgm08_23.cpp (Continuação)
void CountWords(HashTable& table) {
std::string word;
while (cin >> word, !cin.eof ()) {
Object& obj = table.Find(Association (*new String (word)));
if(obj.IsNull ())
table.Insert( *new Association(*new String(word), *new Counter (1)) );
else {
Association& assoc = dynamic_cast<Association&> (obj);
Counter& i = dynamic_cast<Counter&> (assoc.Value ());
++i;
}
}
cout << table << endl;
}
Implementação Java
118
Hierarquia de Classes
119
Tabelas Hash
Interface HashTable// pgm08_06.java
public interface HashTable extends SearchableContainer
{
double getLoadFactor();
}
Aplicação Conta Palavras em Java
Hash com encadeamento em área separada
121
Métodos AbstractHashTable
// pgm08_07.java
public abstract class AbstractHashTableextends AbstractSearchableContainer implements HashTable
{public abstract int getLength();
protected final int f(Object object) {return object.hashCode();
}protected final int g(int x) {
return Math.abs(x) % getLength();}protected final int h(Object object) {
return g( f(object) );}// ...
}
122
Encadeamento Separado
Tabela Hash usando Encadeamento Separado
123
Campos ChainedHashTable
// pgm08_08.java
public class ChainedHashTable extends AbstractHashTable
{
protected LinkedList[] array;
// ...
}
124
Métodos constructor, getLength e purge da classe ChainedHashTable
// pgm08_09.java
public class ChainedHashTable extends AbstractHashTable {protected LinkedList[] array;public ChainedHashTable(int length) {
array = new LinkedList [length];for(int i = 0; i < length; ++i) array[i] = new LinkedList();
}public int getLength() {
return array.length;}public void purge() {
for(int i = 0; i < getLength(); ++i)array[i].purge();count = 0;
}// ...
}
125
Métodos insert e withdraw da classe ChainedHashTable
// pgm08_10.java
public class ChainedHashTable extends AbstractHashTable{
protected LinkedList[] array;public void insert(Comparable object){
array[h (object)].append(object);++count;
}public void withdraw(Comparable object){
array[h (object)].extract(object);--count;
}// ...
}
126
Método find da classe ChainedHashTable
// pgm08_11.java
public class ChainedHashTable extends AbstractHashTable{
protected LinkedList[] array;public Comparable find(Comparable object){
for(LinkedList.Element ptr = array[h(object)].getHead(); ptr != null; ptr = ptr.getNext()){
Comparable datum = (Comparable) ptr.getDatum();if(object.isEQ (datum))
return datum;}return null;
}// ...
}
127
Método getLoadFactor da classe AbstractHashTable
// pgm08_12.java
public abstract class AbstractHashTable
extends AbstractSearchableContainer implements HashTable
{
public abstract int getLength();
public final double getLoadFactor()
{
return (double) getCount() / getLength();
}
// ...
}
Aplicação Conta Palavras em Java
Hash com encadeamento em área primária
129
Hash com encadeamento em área primária
Quando é usado Hash com encadeamento em área primária o transbordamento é tratado por listas encadeadas iniciadas nos “home addresses”.
130
Classe ChainedScatterTable.Entry e campos ChainedScatterTable
// pgm08_13.java
public class ChainedScatterTable extends AbstractHashTable{
protected Entry[] array;static final int nil = -1;protected static final class Entry {
Comparable object;int next = nil;void purge() { object = null; next = nil;}
}// ...
}
131
Métodos constructor, getLength e purge da classe ChainedScatterTable (1)
// pgm08_14.java
public class ChainedScatterTableextends AbstractHashTable
{protected Entry[] array;
public ChainedScatterTable(int length){
array = new Entry [length];for(int i = 0; i < length; ++i) array [i] = new Entry ();
}
132
Métodos constructor, getLength e purge da classe ChainedScatterTable (2)
// pgm08_14.java (Continuação)
public int getLength(){ return array.length;}
public void purge(){ for(int i = 0; i < getLength (); ++i)
array [i].purge(); count = 0;
}// ...
}
133
Métodos insert e find da classe ChainedScatterTable (1)
// pgm08_15.java
public class ChainedScatterTable extends AbstractHashTable{
protected Entry[] array;public void insert(Comparable object) {
if(count == getLength ()) throw new ContainerFullException();int probe = h(object);if(array[probe].object != null) { while(array[probe].next != nil)
probe = array [probe].next; int tail = probe; probe = (probe + 1) % getLength(); while(array[probe].object != null)
probe = (probe + 1) % getLength(); array[tail].next = probe;}
134
// pgm08_15.java (Continuação)
array[probe].object = object;array[probe].next = nil;++count;
}public Comparable find(Comparable object) {
for(int probe = h(object); probe != nil; probe = array [probe].next) {
if( object.isEQ(array[probe].object) ) return array[probe].object;}return null;
}// ...
}
Métodos insert e find da classe ChainedScatterTable (2)
135
Método withdraw da classe ChainedScatterTable (1)
// pgm08_16.java
public class ChainedScatterTable extends AbstractHashTable{
protected Entry[] array;
public void withdraw(Comparable object){
if(count == 0) throw new ContainerEmptyException();int i = h(object);while(i != nil && object != array[i].object) i = array[i].next;if(i == nil) throw new IllegalArgumentException("obj not
found");
136
// pgm08_16.java (Continuação)
for(;;){ int j = array[i].next; while(j != nil) { int h = h(array[j].object);
boolean contained = false; for(int k = array[i].next; k != array[j].next
&& !contained; k = array[k].next) {
if(k == h) contained = true;
}
Método withdraw da classe ChainedScatterTable (2)
137
Método withdraw da classe ChainedScatterTable (3)
// pgm08_16.java (Continuação)
if(!contained) break; j = array[j].next;
} if(j == nil)
break; array[i].object = array[j].object; i = j;}
138
// pgm08_16.java (Continuação)
array[i].object = null;array[i].next = nil;for(int j = (i + getLength () - 1) % getLength (); j != i; j = (j + getLength () - 1) % getLength
()){ if(array[j].next == i) {
array[j].next = nil; break;
}}--count;
}// ...
}
Método withdraw da classe ChainedScatterTable (3)
Aplicação Conta Palavras em Java
Hash usando Endereçamento Aberto
140
Tabelas de Espalhamento usando Endereçamento Aberto (1)
A seqüência de sondagem é uma seqüência de funções
aonde hi é uma função hash hi: K {0,1,...,M-1} A inserção de um item x na tabela de espalhamento é feita
examinando as posições h0(x), h1(x),..., até encontrar uma célula vazia.
A busca de um item na tabela segue a mesma seqüência.As seqüências de sondagem mais comuns são do tipo
para i = 0,1,…,M-1
A função c(i) representa a estratégia de resolução de transbordamentos.
110 ,...,, Mhhh
ii Micxhxh mod))()(()(
141
Tabelas de Espalhamento usando Endereçamento Aberto (2)
Sondagem Linear
Na sondagem linear a função c(i) é linear em i.
Ou, da maneira mais comum
e M devem ser primos relativos.
Para i = 0,1,…,M-1
)()( iic
)()( iic
Mixhhi mod))((
142
Tabelas de Espalhamento usando Endereçamento Aberto (3)
Tabela de Espalhamento usando Endereçamento Aberto e Sondagem Linear
143
OpenScatterTable.Entry e campos OpenScatterTable fields
// pgm08_17.java
public class OpenScatterTable extends AbstractHashTable {protected Entry[] array;static final int empty = 0;static final int occupied = 1;static final int deleted = 2;protected static final class Entry {
int state = empty;Comparable object;void purge() { state = empty; object = null;}
}// ...
}
144
Métodos constructor, getLength e purge da classe OpenScatterTable
// pgm08_18.java
public class OpenScatterTable extends AbstractHashTable {protected Entry[] array;public OpenScatterTable(int length) {
array = new Entry [length];for(int i = 0; i < length; ++i) array[i] = new Entry();}public int getLength() { return array.length;}public void purge() {for (int i = 0; i < getLength (); ++i) array[i].purge();count = 0;
}// ...
}
145
Métodos c, findUnoccupied e insert da classe OpenScatterTable (1)
// pgm08_19.java
public class OpenScatterTable extends AbstractHashTable {
protected Entry[] array;protected static int c(int i) {
return i;}protected int findUnoccupied(Object object) {
int hash = h(object);for(int i = 0; i < count + 1; ++i) { int probe = (hash + c (i)) % getLength(); if(array [probe].state != occupied)
return probe;}throw new ContainerFullException();
}
146
// pgm08_19.java (Continuação)
public void insert(Comparable object){
if(count == getLength ()) throw new ContainerFullException();int offset = findUnoccupied(object);array[offset].state = occupied;array[offset].object = object;++count;
}// ...
}
Métodos c, findUnoccupied e insert da classe OpenScatterTable (2)
147
Métodos findMatch e find da classe OpenScatterTable (1)
//pgm08_20.java
public class OpenScatterTable extends AbstractHashTable{
protected Entry[] array;protected int findMatch(Comparable object) {
int hash = h(object);for(int i = 0; i < getLength (); ++i) { int probe = (hash + c (i)) % getLength(); if(array[probe].state == empty)
break; if(array[probe].state == occupied &&
object.isEQ(array[probe].object)) { return probe;
}}return -1;
}
148
// pgm08_20.java (Continuação)
public Comparable find(Comparable object) {
int offset = findMatch(object);if(offset >= 0) return array[offset].object;else return null;
}// ...
}
Métodos findMatch e find da classe OpenScatterTable (2)
149
Método withdraw da classe OpenScatterTable
//pgm08_21.java
public class OpenScatterTable extends AbstractHashTable {protected Entry[] array;public void withdraw(Comparable object) {
if(count == 0) throw new ContainerEmptyException();int offset = findInstance(object);if(offset < 0) throw new IllegalArgumentException("object not
found");array[offset].state = deleted;array[offset].object = null;--count;
}// ...
}
150
Método OpenScatterTableV2 withdraw (1)
// pgm08_22.java
public class OpenScatterTableV2 extends OpenScatterTable {public void withdraw(Comparable object) {
if(count == 0) throw new ContainerEmptyException();int i = findInstance(object);if(i < 0) throw new IllegalArgumentException("object not found");for(;;) { int j = (i + 1) % getLength(); while(array[j].state == occupied) {
int h = h(array[j].object);if((h <= i && i < j) || (i < j && j < h) || (j < h && h <= i)) break;j = (j + 1) % getLength();
}
151
// pgm08_22.java (Continuação)
if(array[j].state == empty)break;
array[i].state = array[j].state; array[i].object = array[j].object; i = j;}array[i].state = empty;array[i].object = null;--count;
}// ...
}
Método OpenScatterTableV2 withdraw (2)
152
Aplicação Hash/scatter table –contador de palavras (1)
// pgm08_23.java
public class Algorithms{
private static final class Counter extends Int{
Counter(int value){ super(value);}void increment(){ ++value;}
}
153
Aplicação Hash/scatter table –contador de palavras (2)
// pgm08_23.java (Continuação)
public static void wordCounter(Reader in, PrintWriter out) throws IOException
{HashTable table = new ChainedHashTable(1031);StreamTokenizer tin = new StreamTokenizer(in);while(tin.nextToken() != StreamTokenizer.TT_EOF){ String word = tin.sval; Object obj = table.find(new
Association(new Str (word))); if(obj == null) table.insert(new Association(new Str(word),
new Counter(1)));
154
Aplicação Hash/scatter table –contador de palavras (3)
// pgm08_23.java (Continuação)
else { Association assoc = (Association) obj; Counter counter = (Counter)
assoc.getValue(); counter.increment(); }}out.println(table);
}}