Espalhamento

*Sumrio da ApresentaoEspalhamentoA idia inicial de espalhamentoMtodos de EspalhamentoImplementao das funes HashImplementao do EspalhamentoHash com encadeamento em rea separadaHash com encadeamento em rea primriaHash usando Endereamento AbertoAplicao conta palavras (Java)

*Sumrio da ApresentaoEspalhamentoA idia inicial de espalhamentoExemploMtodos de EspalhamentoMtodo da DivisoMtodo do Meio do QuadradoMtodo da MultiplicaoImplementao das funes HashChaves FundamentaisChaves de Ponto FlutuanteChaves de Cadeias de CaracteresEspalhamento de ObjetosEspalhamento de ContainersAssociaes

*Sumrio da ApresentaoHash com encadeamento em rea separadaTabelas Hash Abstratas (s Java)Encadeamento SeparadoImplementaoConstrutor e Destrutor (C++)Construtor e mtodos getLength e purge (Java)Insero e excluso de itensEncontro de itens

Hash com encadeamento em rea primriaTabelas de Espalhamento EncadeadasImplementaoConstrutor e Destrutor (C++)Construtor e mtodos getLength e purge (Java)Insero e encontro de itensExcluso de itens

*Sumrio da ApresentaoHash usando Endereamento AbertoSondagem linearSondagem QuadrticaDuplo HashingImplementaoConstrutor e Destrutor Insero de itensEncontro de itensExcluso de itens

Espalhamento

*Sumrio do item EspalhamentoA idia inicial de espalhamentoExemploMtodos de EspalhamentoMtodo da DivisoMtodo do Meio do QuadradoMtodo da Multiplicao

*A idia inicial de espalhamentoExemplo: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 definio de uma funo 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

*Espalhamento em memria SecundriaO Espalhamento em memria secundria o processo preferencial para a implantao dos arquivos de acesso direto.

*Espalhamento em Memria Secundria1- Agrupar um determinado nmero de registros em uma unidade com endereo comum chamada "bucket".2- Calcular o espao de armazenamento necessrio para o arquivo. Esse dimensionamento do arquivo depende da densidade de empacotamento ou fator de carga que a razo entre o nmero de registros nos arquivos e a capacidade total dos "buckets".3- Escolher uma funo "hash" que a transformao a aplicar chave para obter o endereo do "bucket".4- Optar por uma tcnica de resoluo do problema de transbordamento. Ocorre transbordamento ou "overflow" quando se enderea um registro a um "bucket" j cheio.

*Buckets (1)O arquivo dividido em sees menores denominadas "buckets", que podem conter um ou mais registros. A funo "Hash" atribui a cada registro um endereo de "bucket" ("home address"), onde este pode ser acomodado.O tamanho de bucket determinado pelo nmero de registros que este pode armazenar, ou ainda, pelo nmero de "slots" que ele contm. Um "slot" uma unidade de armazenamento que contm espao 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 caractersticas fsicas do meio de armazenamento. Logo, o tempo de transporte do bucket para a memria principal proporcional ao tamanho do bucket.

*Buckets (2)Ocorre uma coliso quando durante uma incluso de registros, dois deles tm o mesmo endereo calculado pela funo hash. Estes registros so chamados sinnimos. As colises no constituem problemas enquanto no se atingir a capacidade do "bucket" correspondente. A partir da, ocorre transbordamento, que consiste no fato de um registro no poder ser acomodado em "home bucket". Define-se como "home bucket" aquele que est associado ao "home address" do registro, que fora calculado pela funo "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 memria principal mais rpido comparado com o tempo de busca em memria secundria, uma vez que o bucket ser transferido para memria principal.

Mtodos de Espalhamento

*Mtodo do resto da DivisoPara este caso a funo hash h(x) = x mod M, sendo M o nmero de endereos disponveis 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 posio h(x)-1 do array.Os elementos do conjunto K so chamados de chaves. usual armazenar estas chaves em um array ou arquivo.Imediatamente pode-se utilizar esta idia para armazenar no apenas cadeias de caracteres e sim objetos dos quais um dos atributos seja uma chave do conjunto K.A tcnica de "hashing" proporciona uma recuperao de registros extremamente rpida se comparada com a recuperao seqencial. O tempo de recuperao em arquivos sequenciais cresce com o tamanho do arquivo, o que no ocorre com o "hashing". No projeto de um arquivo de acesso direto os fatores que necessrio considerar so os seguintes:

*Mtodo do Meio QuadradoO espalhamento pelo meio do quadrado considera que M = 2k, o nmero de endereos (buckets), um mltiplo de 2. Para palavras de tamanho W, com w bits as operaes inteiras so feitas mdulo W.A funo hash de x obtida elevando x ao quadrado mdulo W e reduzindo este nmero ao domnio {0,1,...,M-1} por meio da multiplicao por dois elevado a w-k o que zera os w-k bits esquerda.

O cdigo que se segue mostra esta implementao

unsigned int const k = 10; // M==1024unsigned int const w = bitsizeof(unsigned int);

unsigned int h(unsigned int x) { return (x * x) >> (w - k);}

*Mtodo da MultiplicaoUma variao do mtodo do meio do quadrado o mtodo da multiplicao, pelo qual hash de x no 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 representao binria 10 011 110 001 101 110 111 100 110 111 001.Sua inversa O cdigo que se segue mostra esta implementaounsigned int const k = 10; // M==1024unsigned int const w = bitsizeof(unsigned int);unsigned int const a = 2654435769U;unsigned int h(unsigned int x);

Implementao das funes Hash

*Sumrio do itemImplementao das funes HashChaves InteirasChaves de Ponto FlutuanteChaves de Cadeias de CaracteresEspalhamento de ObjetosEspalhamento de ContainersAssociaes

*FundamentosAs chaves dos objetos podem ser de quaisquer tipos de dados at estruturas como associaes ou containers.Para um conjunto de chaves, K, e uma constante positiva M, uma funo hash da forma h: K {0,1,..., M-1} conveniente implementar a funo h como uma composio de duas funes f e g. A funo f mapeia chaves em inteiros f: K Z+ aonde Z+ o conjunto dos inteiros no negativos. A funo g mapeia inteiros no negativos em {0, 1, ..., M-1}, g: Z+ {0, 1, ..., M-1}

Desde que sejam conhecidas as funes f e g, a funo hash h definida como a composio delas: h = f g

Ou seja, o valor de hash de uma chave x dado por g(f(x)).

Implementao das funes HashImplementao C++

*Chaves InteirasA funo f que mapeia chaves em inteiros para chaves constitudas de inteiros f(x) = x

Definio da Funo Hash de Inteiros

// pgm08_01.cpp

typedef unsigned int HashValue;

HashValue Hash (char c) { return abs (c); }

HashValue Hash (int i) { return abs (i); }

*Chaves de Ponto FlutuanteTodo real no nulo x pode ser expresso da forma x = m * 2e , sendo A funo f pode ser escrita

Sendo W o maior inteiro que pode ser expresso em uma palavra do computador x e y colidiro se suas mantissas diferirem de menos de 1/2W independente do valor dos expoentes. Definio da Funo 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; }}

*Chaves de Cadeias de CaracteresPara chaves constitudas de cadeias de caracteres pode-se concatenar as representaes dos caracteres. Sendo, por exemplo strings de comprimento 4 , estes strings podem ser transformados em inteiros pela expresso Sendo potncia de 2 pode-se escrever a funo C++: HashValue Hash (string const& s){ return s[0]

*Chaves de Cadeias de CaracteresSendo 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 polinmio em B, os coeficientes do polinmio, si, podem ser calculados pela Regra de Horner, que evita o clculo 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 considerao de polinmio de base 2 semelhante ao deslocamento (shift) basta concatenar os resultados parciais

*Chaves de Cadeias de CaracteresHashValue result = 0;for (unsigned int i = 0; s [i] != 0; ++i) result = result

*Espalhamento de ObjetosUm template da classe Wrapper usado para envelopar instncias de tipos de dados C++ construdos em uma interface abstrata Object. Usando o template as quatro classes Char, Int, Double, and String so declaradas da forma:

typedef Wrapper Char;typedef Wrapper Int;typedef Wrapper Double;typedef Wrapper String;

Como estas classes devem ser concretas devem ter implementaes de todas as funes membros, inclusive a funo Hash.

Definio da funo Menbro Hash da Classe Wrapper

//pgm08_04.cpp template HashValue Wrapper::Hash () const { return ::Hash (datum); }

*Espalhamento de ContainersA funo 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 funo Container::Hash usa a funo Accept para fazer um visitante especial HashingVisitor visitar todos os objetos do container. Quando visita um objeto chama a funo Hash do visitado e acumula o resultado.Definio da funo Membro Hash da Classe Container

*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 ();}

*AssociaesJ que a funo Accept virtual todas as classes derivadas da classe Container fornecero as implementaes correspondentes.Utilizando o conceito de chave pode-se escrever A = {(k,v):kK, v V}A funo hash pode ser expressa como fA(k,v) = fK(k)Sedo fk a funo hash associada ao conjunto K. Uma Association possui dois objetosclass Association : public Object, public Ownership {Object* key;Object* value;...};Para definir a funo hash de uma associao basta chamar a funo membro hash do objeto para o qual a varivel membro key apontaDefinio da Funo Hash Member da classe AssociationHshValue Association::Hash() const{ return key->Hash(): }

Implementao das funes HashImplementao Java

*Mtodo hashCode da classe Int A funo f que mapeia chaves em inteiros para chaves constitudas de inteiros f(x) = x// pgm08_01.java

public class Int extends AbstractObject{protected int value;public int hashCode(){return value;}// ...}

*Mtodo hashCode da classe DblA definio da funo f :

// pgm08_02.java

public class Dbl extends AbstractObject{protected double value;public int hashCode(){long bits = Double.doubleToLongBits(value);return (int)(bits >>> 20);}// ...}

*Chaves de Cadeias de CaracteresPara chaves constitudas de cadeias de caracteres pode-se concatenar as representaes dos caracteres. Sendo, por exemplo strings de comprimento 4 , este string pode ser transformado em inteiro pela expresso Sendo B=27 potncia de 2 pode-se escrever a funo Java: static int f (String s){ return s.charAt(0)

*Chaves de Cadeias de CaracteresSendo 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 polinmio em B, os coeficientes do polinmio, si, podem ser calculados pela Regra de Horner, que evita o clculo 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 considerao de polinmio de base 2 semelhante ao deslocamento (shift) basta concatenar os resultados parciais

*Chaves de Cadeias de Caracteresstatic int f (String s) { int result = 0; for (int i = 0; i < s.length () ; ++i) result = result

*Mtodo 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

*Espalhamento de ContainersA funo 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.

*Mtodo 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 ();}// ...}

*AssociaesJ que a funo Accept virtual todas as classes derivadas da classe Container fornecero as implementaes correspondentes.Utilizando o conceito de chave pode-se escrever

A funo hash pode ser expressa como

Sedo fk a funo hash associada ao conjunto K. Uma Association possui dois objetospublic class Association extends AbstractObject {protected Comparable key; protected Object value;...};Para definir a funo hash de uma associao basta chamar a funo membro hash do objeto para o qual a varivel key membro aponta

*Mtodo hashCode da classe Association// pgm08_05.java

public class Association extends AbstractObject{protected Comparable key;protected Object value;public int hashCode(){return key.hashCode();}// ...}

Implementao do Espalhamento

*Sumrio do item Implantao do EspalhamentoHash com encadeamento em rea separadaTabelas Hash Abstratas (s Java)Encadeamento SeparadoHash com encadeamento em rea primriaTabelas de Espalhamento EncadeadasHash usando Endereamento AbertoSondagem linearSondagem QuadrticaDuplo HashingImplementao

Implementao do EspalhamentoImplementao C++

*Tabelas Hash

Definio 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;};

Implementao do EspalhamentoC++Hash com encadeamento em rea separada

*Tabelas HashDefinio das funes 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 varivel membro de maneira adequada. A funo membro corresponde composio h = g f. A funo membro H recebe como argumento uma referencia constante a um objeto e retorna o resultado Hash modulo length.

*Encadeamento SeparadoTabela Hash usando Encadeamento Separado

*Definio da Classe ChainedHashTable// pgm08_09.cpp

class ChainedHashTable : public HashTable{ Array array;public: ChainedHashTable (unsigned int); // ...};

*Definio das funes Purge Member, Constructor e Destructor da Classe ChainedHashTable (1)// pgm08_10.cpp

ChainedHashTable::ChainedHashTable (unsigned int _length) : HashTable (_length), array (_length) {}

*Definio das funes Purge Member, Constructor e Destructor da Classe ChainedHashTable (2)// pgm08_10.cpp (Continuao)

void ChainedHashTable::Purge(){ for (unsigned int i = 0; i < length; ++i) {if(IsOwner ()) { ListElement const* ptr; for( ptr = array[i].Head (); ptr != 0; ptr = ptr->Next() ) delete ptr->Datum ();}array[i].Purge(); } count = 0;}

ChainedHashTable::~ChainedHashTable () { Purge (); }

*Definio das Funes 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;}

*Definio da Funo Find Member da Classe ChainedHashTable// pgm08_12.cpp

Object& ChainedHashTable::Find (Object const& object) const{ ListElement const* ptr; for(ptr = array [H (object)].Head (); ptr != 0; ptr =ptr->Next()) {if(object == *ptr->Datum ()) return *ptr->Datum (); } return NullObject::Instance ();}

Implementao do EspalhamentoC++Hash com encadeamento em rea primria

*Hash com encadeamento em rea primriaQuando usado Hash com encadeamento em rea primria o transbordamento tratado por listas encadeadas iniciadas nos home addresses.

*Definio da Classe ChainedScatterTable// pgm08_13.cpp

class ChainedScatterTable : public HashTable{ class Entry { public:enum { null = ~0U };Object* object;unsigned int next;

Entry (); };

Array array;public: ChainedScatterTable (unsigned int); // ...};

*Definio das Funes 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) {}

*Definio das Funes Purge Member, Constructor e Destructor da Classe ChainedScatterTable e Constructor da Classe ChainedScatterTable::Entry (2)// pgm08_14.cpp (Continuao)

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 (); }

*Definio das Funes 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; }

*Definio das Funes Insert e Find Member da Classe ChainedScatterTable (2)// pgm08_15.cpp (Continuao)

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();}

*Definio da Funo 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");

*// pgm08_16.cpp (Continuao)

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; }Definio da Funo Withdraw Member da Classe ChainedScatterTable (2)

*Definio da Funo Withdraw Member da Classe ChainedScatterTable (3)// pgm08_16.cpp (Continuao)

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;}

Implementao do EspalhamentoC++Hash usando Endereamento Aberto

*Tabelas de Espalhamento usando Endereamento Aberto (1)A seqncia de sondagem uma seqncia de funes

aonde hi uma funo hash hi: K {0,1,...,M-1}A insero de um item x na tabela de espalhamento feita examinando as posies h0(x), h1(x),..., at encontrar uma clula vazia.A busca de um item na tabela segue a mesma seqncia.As seqncias de sondagem mais comuns so do tipo

para i = 0,1,,M-1A funo c(i) representa a estratgia de resoluo de transbordamentos.

*Tabelas de Espalhamento usando Endereamento Aberto (2)Sondagem Linear

Na sondagem linear a funo c(i) linear em i.

Ou, da maneira mais comum

e M devem ser primos relativos.

Para i = 0,1,,M-1

*Tabelas de Espalhamento usando Endereamento Aberto (3)Tabela de Espalhamento usando Endereamento Aberto e Sondagem Linear

*Tabelas de Espalhamento usando Endereamento Aberto (4)Sondagem Quadrtica

Na sondagem linear a funo c(i) quadrtica em i.


*Tabelas de Espalhamento usando Endereamento Aberto (5)Duplo Hashing

Pode-se gerar uma seqncia de sondagem por meio da tcnica de duplo hashing que usa duas funes h e h .

A seqncia de sondagem obtida da forma

*Definio da Classe OpenScatterTable// pgm08_17.cpp

class OpenScatterTable : public HashTable { class Entry {public:enum State { empty, occupied, deleted };State state;Object* object;Entry (); }; Array 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); // ...};

*Construtores e DestrutoresO construtor default para a classe OpenScatterTable::Entry faz com que uma entrada no ocupada tenha o ponteiro para seu objeto zerada e o estado default de todas as entradas empty. Este construtor default inicializa as duas variveis membro de maneira adequada.

*Definio 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 (); }

*Definio das Funes 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;}

*Definio das Funes 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 funo c define a seqncia de sondagem. Para sondagem linear a funo c a funo identidade.A funo membro FindUnoccupied encontrar uma posio desocupada. A rotina FindUnoccupied sonda o array de acorde com a seqncia de sondagem determinada pela funo c.

*Definio das Funes 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;}

*Definio das Funes FindMatch e Find Member da Classe OpenScatterTable (2)// pgm08_20.cpp (Continuao)

Object& OpenScatterTable::Find (Object const& object) const{ unsigned int const offset = FindMatch (object); if (offset < length)return *array [offset].object; elsereturn NullObject::Instance ();}

*Definio da Funo 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;}

*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

*OpenScatterTable Class Alternate Withdraw Member Function (2)// pgm08_22.cpp (Continuao)

if(array[j].state == Entry::empty) break;array[i] = array[j];i = j; } array[i].state = Entry::empty; array[i].object = 0; --count;}

Implementao Java

Implementao do EspalhamentoJavaHash com encadeamento em rea separada

*Tabelas HashInterface HashTable// pgm08_06.java

public interface HashTable extends SearchableContainer{double getLoadFactor();}

*Mtodos 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) );}// ...}

*Campos ChainedHashTable// pgm08_08.java

public class ChainedHashTable extends AbstractHashTable{protected LinkedList[] array;// ...}

*Mtodos 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;}// ...}

*Mtodos 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;}// ...}

*Mtodo 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;}// ...}

*Mtodo getLoadFactor da classe AbstractHashTable// pgm08_12.java

public abstract class AbstractHashTableextends AbstractSearchableContainer implements HashTable{public abstract int getLength();public final double getLoadFactor(){return (double) getCount() / getLength();}// ...}

Implementao do EspalhamentoJavaHash com encadeamento em rea primria

*

Quando usado Hash com encadeamento em rea primria o transbordamento tratado por listas encadeadas iniciadas nos home addresses. Hash com encadeamento em rea primria

*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;}}// ...}

*Mtodos 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 ();}

*Mtodos constructor, getLength e purge da classe ChainedScatterTable (2)// pgm08_14.java (Continuao)

public int getLength(){ return array.length;}

public void purge(){ for(int i = 0; i < getLength (); ++i) array [i].purge(); count = 0;}// ...}

*Mtodos 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;}

*// pgm08_15.java (Continuao)

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;}// ...}Mtodos insert e find da classe ChainedScatterTable (2)

*Mtodo 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");


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; }Mtodo withdraw da classe ChainedScatterTable (2)

*Mtodo withdraw da classe ChainedScatterTable (3)// pgm08_16.java (Continuao)

if(!contained) break; j = array[j].next; } if(j == nil) break; array[i].object = array[j].object; i = j;}


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;}// ...}Mtodo withdraw da classe ChainedScatterTable (3)

Implementao do EspalhamentoJavaHash usando Endereamento Aberto

*Hash usando endereamento abertoTabela de Espalhamento usando Endereamento Aberto e Sondagem Linear

*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;}}// ...}

*Mtodos 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;}// ...}

*Mtodos 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();}


public void insert(Comparable object){if(count == getLength ()) throw new ContainerFullException();int offset = findUnoccupied(object);array[offset].state = occupied;array[offset].object = object;++count;}// ...}Mtodos c, findUnoccupied e insert da classe OpenScatterTable (2)

*Mtodos 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;}


public Comparable find(Comparable object) {int offset = findMatch(object);if(offset >= 0) return array[offset].object;else return null;}// ...}

Mtodos findMatch e find da classe OpenScatterTable (2)

*Mtodo 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;}// ...}

*Mtodo 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


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;}// ...}Mtodo OpenScatterTableV2 withdraw (2)

AplicaoJava

*Aplicao 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;}}

*Aplicao Hash/scatter table contador de palavras (2) // pgm08_23.java (Continuao)

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)));

*Aplicao Hash/scatter table contador de palavras (3)// pgm08_23.java (Continuao)

else { Association assoc = (Association) obj; Counter counter = (Counter) assoc.getValue(); counter.increment(); }}out.println(table);}}

*AplicaesAplicao da Hash/Scatter Table--Contando Palavras

Uma aplicao de espalhamento a contagem do nmero de ocorrncias distintas de cada palavra contida em um arquivo texto.

AplicaesAplicao da Hash/Scatter Table--Contando Palavras (1)

//pgm08_23.cpp

class Counter : public Int {public: Counter (int i) : Int(i) {} void operator ++ () { ++datum; }};

*AplicaesAplicaesAplicao da Hash/Scatter Table--Contando Palavras (2)// pgm08_23.cpp (Continuao)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 (obj); Counter& i = dynamic_cast (assoc.Value ()); ++i;} } cout

Implementao Java

*Hierarquia de Classes

*Tabelas HashInterface HashTable// pgm08_06.java

public interface HashTable extends SearchableContainer{double getLoadFactor();}

Aplicao Conta Palavras em JavaHash com encadeamento em rea separada

*Mtodos 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) );}// ...}

*Campos ChainedHashTable// pgm08_08.java

public class ChainedHashTable extends AbstractHashTable{protected LinkedList[] array;// ...}

*Mtodos 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;}// ...}

*Mtodos 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;}// ...}

*Mtodo 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;}// ...}

*Mtodo getLoadFactor da classe AbstractHashTable// pgm08_12.java

public abstract class AbstractHashTableextends AbstractSearchableContainer implements HashTable{public abstract int getLength();public final double getLoadFactor(){return (double) getCount() / getLength();}// ...}

Aplicao Conta Palavras em JavaHash com encadeamento em rea primria

*Hash com encadeamento em rea primriaQuando usado Hash com encadeamento em rea primria o transbordamento tratado por listas encadeadas iniciadas nos home addresses.

*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;}}// ...}

*Mtodos 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 ();}

*Mtodos constructor, getLength e purge da classe ChainedScatterTable (2)// pgm08_14.java (Continuao)

public int getLength(){ return array.length;}

public void purge(){ for(int i = 0; i < getLength (); ++i) array [i].purge(); count = 0;}// ...}

*Mtodos 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;}


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;}// ...}Mtodos insert e find da classe ChainedScatterTable (2)

*Mtodo 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");


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; }Mtodo withdraw da classe ChainedScatterTable (2)

*Mtodo withdraw da classe ChainedScatterTable (3)// pgm08_16.java (Continuao)

if(!contained) break; j = array[j].next; } if(j == nil) break; array[i].object = array[j].object; i = j;}


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;}// ...}Mtodo withdraw da classe ChainedScatterTable (3)

Aplicao Conta Palavras em JavaHash usando Endereamento Aberto

*Tabelas de Espalhamento usando Endereamento Aberto (1)A seqncia de sondagem uma seqncia de funes

aonde hi uma funo hash hi: K {0,1,...,M-1}A insero de um item x na tabela de espalhamento feita examinando as posies h0(x), h1(x),..., at encontrar uma clula vazia.A busca de um item na tabela segue a mesma seqncia.As seqncias de sondagem mais comuns so do tipo

para i = 0,1,,M-1A funo c(i) representa a estratgia de resoluo de transbordamentos.

*Tabelas de Espalhamento usando Endereamento Aberto (2)Sondagem Linear

Na sondagem linear a funo c(i) linear em i.


e M devem ser primos relativos.

Para i = 0,1,,M-1