Criando metodo para tratamento de colisao

Programação Java
#1

[code]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());

    }

}[/code]

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

#2

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?

#3

[code]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("]");
	}
}

}
[/code]

#4

O que foi essa resposta um ano depois?

#5