Class SequentialSearchST<Key,Value>

java.lang.Object

SequentialSearchST<Key,Value>

public class SequentialSearchST<Key,Value>
extends java.lang.Object

The SequentialSearchST class represents an (unordered) symbol table of generic (key,value) pairs. It supports the usual put(), get(), contains(), delete(), size(), and isEmpty() methods. It also provides a keys() method for iterating over all of the keys.

A classe SequentialSearchST implementa uma tabela de símbolos (não ordenada) de pares (chave,valor) genéricos. Ela dá suporte aos métodos put(), get(), contains(), delete(), size(), e isEmpty() usuais.

Conventions: When associating a value with a key that is already in the symbol table, the old value is replaced with the new. Values cannot be null; setting the value associated with a key to null has the effect of deleting the key from the table.

Convenções: Quando associa um valor com uma chave que já está na tabela, o valor antigo é substituído pelo novo. Além disso, valores não podem ser null; atribuir null ao valor associado com uma chave tem o efeito de remover a chave da tabela.

This implementation uses a singly-linked list and sequential search. It relies on the equals() method to test whether two keys are equal. It does not call either the compareTo() or hashCode() method. The put() and delete() operations take linear time; the get() and contains() operations takes linear time in the worst case. The size(), and isEmpty() operations take constant time. Construction takes constant time.

Esta implementação usa uma lista ligada simples e busca sequencial. Ela depende do método equals() para verificar se duas chaves são iguais. Ela não invoca o método compareTo() nem o método hashCode(). As operações put() e delete() consomem tempo linear; as operações get() e contains() consomem tempo linear no pior caso. As operações size() e isEmpty() consomem tempo constante. A construção consome tempo constante.

For additional documentation, see Section 3.1 of "Algorithms, 4th Edition", by Robert Sedgewick and Kevin Wayne.

Para documentação adicional, veja a Seção 3.1 de "Algorithms, 4a edição" de Robert Sedgewick e Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
SequentialSearchST() Initializes an empty symbol table.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	contains(Key key) Does this symbol table contain the given key?
void	delete(Key key) Removes the key and associated value from the symbol table if the key is in the symbol table.
Value	get(Key key) Returns the value associated with the given key.
boolean	isEmpty() Is this symbol table empty?
java.lang.Iterable<Key>	keys() Returns all keys in the symbol table as an Iterable.
static void	main(java.lang.String[] args) Unit tests the SequentialSearchST data type.
void	put(Key key, Value val) Inserts the (key, val) pair into the symbol table, overwriting the old value with val if the key is already in the symbol table.
int	size() Returns the number of (key, value) pairs in this symbol table.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SequentialSearchST

public SequentialSearchST()

Initializes an empty symbol table. Inicializa uma tabela de símbolos vazia.

Method Detail

size

public int size()

Returns the number of (key, value) pairs in this symbol table. Devolve o número de pares (chave,valor) nesta tabela de símbolos.

isEmpty

public boolean isEmpty()

Is this symbol table empty?

contains

public boolean contains(Key key)

Does this symbol table contain the given key?

get

public Value get(Key key)

Returns the value associated with the given key. Returns null if the key is not in the symbol table.

put

public void put(Key key,
       Value val)

Inserts the (key, val) pair into the symbol table, overwriting the old value with val if the key is already in the symbol table. If val is null, deletes the key from the table.

delete

public void delete(Key key)

Removes the key and associated value from the symbol table if the key is in the symbol table. Does nothing if key is not in the table.

keys

public java.lang.Iterable<Key> keys()

Returns all keys in the symbol table as an Iterable. To iterate over all of the keys in a symbol table named st, use the foreach notation: for (Key key : st.keys()).

main

public static void main(java.lang.String[] args)

Unit tests the SequentialSearchST data type. Builds a symbol table whose keys are strings. Reads the keys from standard input and assigns value i to the i-th key read. Then prints all (key, value) pairs.