Hash Table List - Tabela Hash com colisão Lista em Java

HashTableLista.java

/* Criado por: profa. Divani Barbosa Gavinier
   Curriculo Lattes: http://lattes.cnpq.br/8503400830635447
   [email protected]
*/
import java.io.*;   // pacote contem classe Scanner
import java.util.*; // pacote contem System.in
import java.lang.*; // pacote contem Math.abs()

class No {
   public double item;
   public No prox; // proximo no da lista
   
   public No(double valor) { item=valor; } // construtor
   
   public void mostra() { System.out.print(item + " -> "); }
}
//////////////////////////////////////////////////
class Lista {
  private No primeiro; // referencia ao primeiro Nó da lista

  public Lista() { primeiro=null; }  // Construtor

  public boolean empty() { return (primeiro==null); }

  public void insere_lista(double v) {
    No lista = new No(v); // Alocando memoria para o Nó
    if ( empty() ) { // Se a lista estiver vazia
       lista.prox = null;
       primeiro = lista;
       return;
    }
    No atual = primeiro;
    while(atual.prox != null) // caminhando para o ultimo Nó da lista
       atual = atual.prox;
    atual.prox = lista;
    lista.prox = null;
  }

  public void imprime_lista() {
    No atual = primeiro;
    while (atual != null) {   // caminhando para o fim da lista
      atual.mostra();
      atual = atual.prox;
    }
  }
  
  public boolean busca_lista(double chave) {
    No atual = primeiro;
    while (atual!=null) {  // caminhando para o fim da lista
      if(atual.item == chave) return true;
      atual = atual.prox;
    }
    return false;
  }
  
  public void apaga_lista(double valor) {  // Apaga item recebido no parametro
    if (!busca_lista(valor)) {
      System.out.println(" *** ATENCAO item NAO encontrado ***");
      return;
    }
    No atual, anterior;
    atual = anterior = primeiro;
    while (atual!=null) { // caminhando para o fim da lista
      if(atual.item == valor) break;
      anterior = atual;
      atual = atual.prox;
    }
    if (atual == primeiro) primeiro = primeiro.prox;
    else anterior.prox = atual.prox;
  }
  
}
//////////////////////////////////////////////////////
class HashLista {

  private Lista[] tab;
  private int TAM_MAX;

  public HashLista(int tam) {
    tab = new Lista[tam];
    TAM_MAX = tam;
    for(int i=0; i<tam; i++)   // inicializando
        tab[i] = null;
  }
  
  private int funcaohash(double chave) {
        int v = (int) chave;
	return ( Math.abs(v) % TAM_MAX );
  }
  
  public void insere(double item) {
     int pos = funcaohash(item);
     if ( tab[pos]!=null ) { // se esta ocupado
	if (tab[pos].busca_lista(item)) { // verificando se a chave ja existe
	   System.out.println(" *** ATENCAO O item " + item + " ja foi cadastrado ***");
	   return;
	}
     }
     else  // se estiver livre
        tab[pos] = new Lista();

     tab[pos].insere_lista(item);
  }

  public void apaga(double chave) {
    int pos = busca(chave);
    if (pos != -1) {
       tab[pos].apaga_lista(chave);
    }
    else System.out.println("\n Item nao encontrado");
  }

  public void imprime() {
    for (int i=0; i<TAM_MAX; i++) { 
       System.out.print("\n HASH[" + i + "] -> ");
       if ( tab[i]!=null )
          tab[i].imprime_lista();
       System.out.print("null");
    }
  }
  
  public int busca(double chave) {
    for (int i=0; i<TAM_MAX; i++)
       if ( tab[i]!=null )
          if ( tab[i].busca_lista(chave) ) return i;
    return -1;
  }

}
//////////////////////////////////////////////////////
class HashTableLista {
  public static void main(String[] args) {
    HashLista tab = new HashLista(7);
    Scanner le = new Scanner(System.in);
    double item;

    System.out.println("\n*********************************************************************");
    System.out.println("Tabela HASH com tratamento de colisoes Lista (7 itens reais - double)");
    System.out.println("*********************************************************************");
    System.out.println(" Inserindo 10 elementos ");
    for (int i=0; i<10; i++){
	System.out.print(" Inserindo elemento " + (i+1) );
	System.out.print(" - Forneca valor real: ");
	item = le.nextDouble();
	tab.insere(item);
    }

    System.out.print("\n Imprimindo conteudo");
    tab.imprime();
    
    while(true) {
      System.out.print("\n\n>> Forneca o item que deseja apagar (-1 sai): ");
      item = le.nextDouble();
      if (item == -1) break;
      tab.apaga(item);
      tab.imprime();
    }

    System.out.println("\n");
  }
}