Advertisement
Guest User

Estrutura de Dados - Java - Hashing Simples

a guest
Oct 17th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.43 KB | None | 0 0
  1. package Utils;
  2.  
  3. import java.util.Random;
  4.  
  5. public class HashVec
  6. {
  7.     private int   FreeAddrKey         = -1;
  8.     private int   FreeSpace           = 100;
  9.     private int   FreeSpaceMultiplier = 3;
  10.     private int[] HashTable           = new int[FreeSpace * FreeSpaceMultiplier];
  11.     private int   StaticValues[]      = { 383, 487, 235, 527, 510, 320, 203, 108, 563, 500, 646, 103 };
  12.    
  13.     public void InitializeVector()
  14.     {
  15.         for (int iV = 0; iV < this.FreeSpace * FreeSpaceMultiplier; iV++)
  16.         {
  17.             this.HashTable[iV] = FreeAddrKey;
  18.         }
  19.     }
  20.    
  21.     public int GetAddr(int Value)
  22.     {
  23.         return (Value % this.FreeSpace) + 1;
  24.     }
  25.    
  26.     public void FreeAddr(int Addr)
  27.     {
  28.         this.HashTable[Addr] = FreeAddrKey;
  29.     }
  30.    
  31.     public int FindAddr(int Value)
  32.     {
  33.         int Addr = GetAddr(Value);
  34.        
  35.         if (this.HashTable[Addr] == Value)
  36.         {
  37.             return Addr;
  38.            
  39.         } else
  40.         {
  41.             int NextAddr = 1;
  42.             while (true)
  43.             {
  44.                 if ((Addr + NextAddr) <= ((this.FreeSpace * this.FreeSpaceMultiplier) - 1))
  45.                 {
  46.                     if (this.HashTable[Addr + NextAddr] == Value)
  47.                     {
  48.                         // Found.
  49.                         break;
  50.                        
  51.                     } else
  52.                     {
  53.                         NextAddr++;
  54.                         continue;
  55.                     }
  56.                    
  57.                 } else
  58.                 {
  59.                     this.PrintLine("Memory Allocation failed: insufficient space.");
  60.                     break;
  61.                 }
  62.             }
  63.         }
  64.        
  65.         return 0;
  66.     }
  67.    
  68.     public void FillStatic()
  69.     {
  70.         for (int sT = 0; sT < StaticValues.length; sT++)
  71.         {
  72.             int Value = StaticValues[sT];
  73.             int Addr  = GetAddr(Value);
  74.            
  75.             if (this.HashTable[Addr] == FreeAddrKey)
  76.             {
  77.                 this.HashTable[Addr] = Value;
  78.                 this.LogInsertion(Addr, Value, 0);
  79.            
  80.             } else
  81.             {
  82.                 int NextAddr = 1;
  83.                 while (true)
  84.                 {
  85.                     if ((Addr + NextAddr) <= ((this.FreeSpace * this.FreeSpaceMultiplier) - 1))
  86.                     {
  87.                         if (this.HashTable[Addr + NextAddr] != FreeAddrKey)
  88.                         {
  89.                             this.HashTable[Addr + NextAddr] = Value;
  90.                             this.LogInsertion(Addr, Value, NextAddr - 1);
  91.                             break;
  92.                            
  93.                         } else
  94.                         {
  95.                             NextAddr++;
  96.                             continue;
  97.                         }
  98.                        
  99.                     } else
  100.                     {
  101.                         this.PrintLine("Memory Allocation failed: insufficient space.");
  102.                         break;
  103.                     }
  104.                 }
  105.             }
  106.         }
  107.     }
  108.    
  109.     public void FillRandom(int MaxValueRange)
  110.     {
  111.         int zV = this.FreeSpace;
  112.         while (zV != 0)
  113.         {
  114.             Random RandomInt = new Random();
  115.             int Value        = RandomInt.nextInt(MaxValueRange);
  116.             int Addr         = GetAddr(Value);
  117.            
  118.             if (this.HashTable[Addr] == FreeAddrKey)
  119.             {
  120.                 this.HashTable[Addr] = Value;
  121.                 this.LogInsertion(Addr, Value, 0);
  122.            
  123.             } else
  124.             {
  125.                 int NextAddr = 1;
  126.                 while (true)
  127.                 {
  128.                     if ((Addr + NextAddr) <= ((this.FreeSpace * this.FreeSpaceMultiplier) - 1))
  129.                     {
  130.                         if (this.HashTable[Addr + NextAddr] != FreeAddrKey)
  131.                         {
  132.                             this.HashTable[Addr + NextAddr] = Value;
  133.                             this.LogInsertion(Addr, Value, NextAddr - 1);
  134.                             break;
  135.                            
  136.                         } else
  137.                         {
  138.                             NextAddr++;
  139.                             continue;
  140.                         }
  141.                        
  142.                     } else
  143.                     {
  144.                         this.PrintLine("Memory Allocation failed: insufficient space.");
  145.                         break;
  146.                     }
  147.                 }
  148.             }
  149.            
  150.             zV--;
  151.         }
  152.     }
  153.    
  154.     public void PrintLine(String Line)
  155.     {
  156.         System.out.println(Line);
  157.     }
  158.    
  159.     public void LogInsertion(int Addr, int Value, int Colisions)
  160.     {
  161.         PrintLine("Addr: " + Addr + " Value: " + Value + " Colisions: " + Colisions);
  162.     }
  163.    
  164.     public void ShowVector(int[] Vector)
  165.     {
  166.         for (int sV = 0; sV < (FreeSpace * FreeSpaceMultiplier) - 1; sV++)
  167.         {
  168.             PrintLine("Addr: " + sV + " Value: " + Vector[sV]);
  169.         }
  170.     }
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement