Tabela Hash

TabelaHash.java

public class TabelaHash {

	private Registro[] registros = new Registro[10];

	public void put(Object chave, String valor) {
		int posicao = hash(chave);

		//Se ainda não existem registros nesta linha do hash
		if (registros[posicao] == null) { 
			registros[posicao] = novoRegistro(chave, valor);

		//Se se já houver registros nesta linha do hash
		} else {
			//Pega o primeiro registro da linha
			Registro atual = registros[posicao]; 
			
			//Caminha até o último registro
			while (atual.getProximo() != null) {
				
				//Se achar a mesma chave "no meio do caminho", 
				//troca o valor e acaba o método
				if (atual.getChave().equals(chave)) {
					atual.setValor(valor);
					return;
				}
				
				atual = atual.getProximo();
			}
			
			//Se achar a mesma chave "no final do caminho", 
			//troca o valor e acaba o método
			if (atual.getChave().equals(chave)) {
				atual.setValor(valor);
				return;
			}

			//Se chegar no final da lista desta linha, adiciona um 
			//novo registro com a chave, o valor, e colocando o próximo como nulo
			atual.setProximo(novoRegistro(chave, valor));
		}

		
	}

	protected Registro novoRegistro(Object chave, String valor) {
		Registro novoRegistro = new Registro();
		novoRegistro.setChave(chave);
		novoRegistro.setValor(valor);
		novoRegistro.setProximo(null);
		return novoRegistro;
	}

	private int hash(Object chave) {
		return chave.hashCode() % 10;
	}

	public String get(Object chave) {
		//Mapeia a chave para uma posição de linha (no hash)
		int posicao = hash(chave);
		Registro atual = registros[posicao];
		
		//A linha da chave procurada está nula
		if (atual == null) {
			throw new RuntimeException("Chave desconhecida: " + chave);
		}
		
		//Caminha na linha, procurando a chave
		while (!atual.getChave().equals(chave)) {
			
			//Se chegar no final da linha, não encontrou a chave
			if (atual.getProximo() == null) {
				throw new RuntimeException("Chave desconhecida: " + chave);
			}
			atual = atual.getProximo();
		}
		
		return atual.getValor();
	}

}

class Registro {

	private Object chave;
	private String valor;
	private Registro proximo;

	public Object getChave() {
		return chave;
	}

	public void setChave(Object chave) {
		this.chave = chave;
	}

	public String getValor() {
		return valor;
	}

	public void setValor(String valor) {
		this.valor = valor;
	}

	public Registro getProximo() {
		return proximo;
	}

	public void setProximo(Registro proximo) {
		this.proximo = proximo;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((chave == null) ? 0 : chave.hashCode());
		result = prime * result + ((proximo == null) ? 0 : proximo.hashCode());
		result = prime * result + ((valor == null) ? 0 : valor.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Registro other = (Registro) obj;
		if (chave == null) {
			if (other.chave != null)
				return false;
		} else if (!chave.equals(other.chave))
			return false;
		if (proximo == null) {
			if (other.proximo != null)
				return false;
		} else if (!proximo.equals(other.proximo))
			return false;
		if (valor == null) {
			if (other.valor != null)
				return false;
		} else if (!valor.equals(other.valor))
			return false;
		return true;
	}

	
	
}

TabelaHashTest.java

import static org.junit.Assert.*;

import org.junit.Test;

public class TabelaHashTest {

	@Test
	public void semColisao() {
		TabelaHash tabela = new TabelaHash();
		
		tabela.put(831, "João Pessoa");
		tabela.put(832, "Campina Grande");
		tabela.put(810, "Recife");
		tabela.put(713, "Salvador");
		tabela.put(115, "São Paulo");
		
		assertEquals("Campina Grande", tabela.get(832));
	}
	
	@Test
	public void comColisao() {
		TabelaHash tabela = new TabelaHash();

		tabela.put(831, "João Pessoa");
		tabela.put(832, "Campina Grande");
		tabela.put(811, "Recife");
		tabela.put(711, "Salvador");
		tabela.put(111, "São Paulo");
	
		assertEquals("Campina Grande", tabela.get(832));
		assertEquals("Salvador", tabela.get(711));
	}
	
	
	@Test
	public void alterarValor() {
		TabelaHash tabela = new TabelaHash();

		tabela.put("831", "João Pessoa");
		tabela.put("832", "Campina Grande");
		tabela.put("811", "Recife");
		tabela.put("711", "Salvador");
		tabela.put("111", "São Paulo");
		tabela.put("831", "Parahyba");
		tabela.put("811", "Nassau");
		tabela.put("832", "Rainha da Borborema");
	
		assertEquals("Parahyba", tabela.get("831"));
		assertEquals("Nassau", tabela.get("811"));
		assertEquals("Rainha da Borborema", tabela.get("832"));
	}

}