Criando metodo para tratamento de colisao

3 respostas
L
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TabelaHash {

	private List<List<Cliente>> tabela = new ArrayList<List<Cliente>>();
	private int tamanho = 0;

	private int calculaIndice(Cliente cliente) {
		return Math.abs(cliente.hashCode()) % tabela.size();
	}

	public TabelaHash() {
		for (int i = 0; i < 10; i++) {
			LinkedList<Cliente> lista = new LinkedList<Cliente>();
			tabela.add(lista);
		}
	}

	public List<Cliente> pegaTodos() {
		List<Cliente> alunos = new ArrayList<Cliente>();
		for (int i = 0; i < this.tabela.size(); i++) {
			alunos.addAll(this.tabela.get(i));
		}
		return alunos;
	}

	private void redimensionaTabela(int novaCapacidade) {
		List<Cliente> clientes = this.pegaTodos();
		this.tabela.clear();
		for (int i = 0; i < novaCapacidade; i++) {
			this.tabela.add(new LinkedList<Cliente>());
		}
		this.tamanho = 0;
		for (Cliente cliente : clientes) {
			this.adiciona(cliente);
		}
	}

	private void verificaCarga() {
		int capacidade = this.tabela.size();
		double carga = (double) this.tamanho / capacidade;
		if (carga > 0.75) {
			this.redimensionaTabela(capacidade * 2);
		} else if (carga < 0.25) {
			this.redimensionaTabela(Math.max(capacidade / 2, 10));
		}
	}

	public void adiciona(Cliente cliente) {
		if (!this.contem(cliente)) {
			this.verificaCarga();
		}
		int indice = this.calculaIndice(cliente);
		List<Cliente> lista = this.tabela.get(indice);
		lista.add(cliente);
		this.tamanho++;
	}

	public void remove(Cliente cliente) {
		if (this.contem(cliente)) {
			int indice = this.calculaIndice(cliente);
			List<Cliente> lista = this.tabela.get(indice);
			Cliente Cliente;
			for (int i = 0; i < lista.size(); i++) {
				Cliente = lista.get(i);
				if (Cliente.getCodigo() == cliente.getCodigo()) {
					lista.remove(i);
				}
			}
			this.tamanho--;
			this.verificaCarga();
		}
	}

	private boolean contem(Cliente cliente) {
		int indice = this.calculaIndice(cliente);
		List<Cliente> lista = this.tabela.get(indice);
		Cliente Cliente;
		for (int i = 0; i < lista.size(); i++) {
			Cliente = lista.get(i);
			if (Cliente.getCodigo() == cliente.getCodigo()) {
				return true;
			}
		}
		return false;
	}

	public Cliente pegaItem(Cliente cliente) {
		Cliente clienteBusca = null;
		int indice = this.calculaIndice(cliente);
		List<Cliente> lista = this.tabela.get(indice);
		for (int i = 0; i < lista.size(); i++) {
			clienteBusca = lista.get(i);
			if (clienteBusca.getCodigo() == cliente.getCodigo()) {
				break;
			}
		}
		return clienteBusca;
	}

	public int tamanho() {
		return this.tamanho;
	}

	public void imprimeTabela() {
		for (List<Cliente> lista : this.tabela) {
			System.out.print("[");
			for (int i = 0; i < lista.size(); i++) {
				System.out.print(lista.get(i).getNome() + ((i + 1 != lista.size()) ? " | " : "") );	

			
			}
			System.out.println("]");
		}
	}

}



public class Principal { 

        public static void main(String[] args) {
                TabelaHash hash = new TabelaHash();
                Cliente c1 = new Cliente(60394, "Alexandre");
                Cliente c2 = new Cliente(60395, "Rogério");
                Cliente c3 = new Cliente(60395, "Jose");
                Cliente c4 = new Cliente(60396, "Maria");
                Cliente c5 = new Cliente(60397, "Ana");
                Cliente c6 = new Cliente(60398, "Marcelo");

                hash.adiciona(c1);
                hash.adiciona(c2);
                hash.adiciona(c3);
                hash.adiciona(c4);
                hash.adiciona(c5);
                hash.adiciona(c6);

                System.out.println("Tamanho da tabela: " + hash.tamanho());
                hash.imprimeTabela();
                System.out.println("-----------------------------------------");

                Cliente cliente = new Cliente(60397, "");
                hash.remove(cliente);
                System.out.println("Aluno 60397 removido.");
                System.out.println("Tamanho da tabela: " + hash.tamanho());
                hash.imprimeTabela();
                System.out.println("-----------------------------------------");

                System.out.println("Pesquisa pelo código 60395");
                cliente.setCodigo(60395);
                System.out.print(hash.pegaItem(cliente).getNome());

        }

}

Como posso implementar o metodo para tratamento de colisao, pois c2 e c3 caem na mesma posicao queria fazer como que os dois fossem colocados em posicoes diferentes

Muito Obrigado pela ajuda

3 Respostas

ViniGodoy

Não é responsabilidade do hashtable tratar colisões.

Você tem 2 alternativas:

  1. C2 e C3 deveriam calcular o hashCode de maneira diferente do que simplesmente pelo id;
  2. Você precisa implementar corretamente o método equals. Assim, clientes diferentes com mesmo hash ocuparão o mesmo índice na tabela, mas serão considerados elementos diferentes na lista que a tabela aponta.

Ah sim, e geralmente uma tabela hash mapeia uma chave a um valor…
No caso caso, você está mapeando o cliente ao que?

PS: O exercício é criar a tabela hash, ou você não conhece a classe HashMap?

C
package estrutura;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class ConjuntoEspalhamento {

	private List<List<Object>> tabela = new ArrayList<List<Object>>();
	
	private int tamanho = 0;

	public ConjuntoEspalhamento() {
		for (int i = 0; i < 26; i++) {
			LinkedList<Object> lista = new LinkedList<Object>();
			tabela.add(lista);
		}
	}

	public void adiciona(Object objeto) {
		if (!this.contem(objeto)) {
			this.verificaCarga();
			int indice = this.calculaIndiceDaTabela(objeto);
			List<Object> lista = this.tabela.get(indice);
			lista.add(objeto);
			this.tamanho++;
		}
	}

	public void remove(Object objeto) {
		if (this.contem(objeto)) {
			int indice = this.calculaIndiceDaTabela(objeto);
			List<Object> lista = this.tabela.get(indice);
			lista.remove(objeto);
			this.tamanho--;
			this.verificaCarga();
		}
	}

	public List<Object> pegaTodos() {
		List<Object> objetos = new ArrayList<Object>();
		for (int i = 0; i < this.tabela.size(); i++) {
			objetos.addAll(this.tabela.get(i));
		}
		return objetos;
	}

	public boolean contem(Object objeto) {
		int indice = this.calculaIndiceDaTabela(objeto);
		List<Object> lista = this.tabela.get(indice);
		return lista.contains(objeto);
	}

	public int tamanho() {
		return this.tamanho;
	}

	private int calculaIndiceDaTabela(Object objeto) {
		int codigoDeEspalhamento = objeto.hashCode();
		codigoDeEspalhamento = Math.abs(codigoDeEspalhamento);
		return codigoDeEspalhamento % tabela.size();
	}

	private void redimensionaTabela(int novaCapacidade) {
		List<Object> objetos = this.pegaTodos();
		this.tabela.clear();
		for (int i = 0; i < novaCapacidade; i++) {
			this.tabela.add(new LinkedList<Object>());
		}
		for (Object objeto : objetos) {
			this.adiciona(objeto);
		}
	}

	private void verificaCarga() {
		int capacidade = this.tabela.size();
		double carga = (double) this.tamanho / capacidade;
		if (carga > 0.75) {
			this.redimensionaTabela(capacidade * 2);
		} else if (carga < 0.25) {
			this.redimensionaTabela(Math.max(capacidade / 2, 10));
		}
	}

	public void imprimeTabela() {
		for (List<Object> lista : this.tabela) {
			System.out.print("[");
			for (int i = 0; i < lista.size(); i++) {
				System.out.print("*");
			}
			System.out.println("]");
		}
	}

}
ViniGodoy

O que foi essa resposta um ano depois?

Criado 21 de junho de 2008
Ultima resposta 31 de jul. de 2009
Respostas 3
Participantes 3