哈希表-开放地址法之线性探测

**哈希表
优点：速度快（插入和查找）
缺点：基于数组，不能有序的遍历
键值对存储方式，通过键来访问值
hashMap.put( key , value );

解决哈希冲突有两种方法：
开放地址法
链地址法

线性探测属于开放地址法

线性探测插入演示：
数组最初状态

在这组数据中要插入83

先对要插入数据哈希化，哈希化后的数据就是数组下标，这里哈希化后的数据是23

然后发现23已经有数据了，产生冲突，线性探测的解决方案是依次递增，直到找到空位


**

package map;

/*
 * 2017年12月19日17:04:18
 *
 * 哈希表
 *
 * 解决哈希冲突的方法为开放地址法（线性探测）
 */
public class HashApp
{
   public dataItem [] arr ;//哈希表的底层是由数组实现的
   public int size ;//当前数组的最大长度
   public dataItem newItem ;//新插入的节点
   public int currentSize ;//当前数组有几个元素

   //初始化
   public HashApp ( int maxSize )
   {
      arr = new dataItem [maxSize] ;
      size = maxSize ;
      currentSize = 0 ;
   }

   //哈希化
   public int hash ( int value )
   {
      //返回哈希化后的索引下标
      return value % size ;
   }

   //添加新数据
   public void insert ( int data )
   {
      //如果满了，直接返回
      if ( isFull () )
      {
         System.out.println ( "hashmap is full" );
         return ;
      }

      int index = hash ( data ) ;//计算哈希化后的索引
      newItem = new dataItem ( data ) ;

      //当前下标中元素不为空，说明有元素了，index递增
      while ( arr [index] != null )
      {
         index ++ ;
         index = hash(index) ;//防止index超过数组最大索引下标
      }

      arr [index] = newItem ;//退出循环，说明找到空位了，放进去
      ++ currentSize ;

   }

   //删除数据
   public void delete ( int data )
   {
      int index = hash ( data ) ;

      while ( arr [index] != null )
      {
         if ( arr [index].getValue () == data  )
         {
           arr [index] = null ;
           return ;
         }

         index ++ ;
         index = hash (index) ;
      }
   }

   //查找数据
   public dataItem find ( int value )
   {
      int index = hash ( value ) ;

      while ( arr [index] != null )
      {
         if ( arr [index].getValue () == value  )
         {

           return arr [index];
         }

         index ++ ;
         index = hash (index) ;
      }

      return null ;
   }

   //判断数组是否满
   public boolean isFull ()
   {
      return currentSize  == size ;
   }


   //哈希表无法有序的遍历！

   //所以这里遍历只是查看一个数据的分布情况
   public void display ()
   {
      for ( int i = 0 ; i < arr.length ; ++i )
      {
         if ( arr [ i] != null)
         System.out.print ( arr [i].getValue () +" ");
      }
      System.out.println (  );
   }
}

---------------------------------------------
package map;

public class dataItem
{
   private int value ;

   public dataItem ( int value )
   {
      this.value = value ;
   }

   public int getValue ()
   {
      return value ;
   }

   public void setValue ( int value )
   {
      this.value = value ;
   }
}