Хэрэглэгчийн яриа:Sw12d012

                                          Хэш функц

Эхний алхамд түлхүүрийг хүснэгтийн хаяг руу хувиргах хэш функц тодорхойлох ёстой . Энэ процесс нь санамсаргүй тоо үүсгэхдээ төстэй арифметик үйлдэл юм. Өөрөөр хэлбэл к түлхүүрийг олонлогийг [0,м-1] гэсэн (м хүснэгтийн хэмжээ) мужийн хооронд бүхэл тоонууд руу хувиргах н:к-ээс м функцийг тодорхойлох болно. Н функцыг тодорхойлоход 2 үндсэн шалгуурыг баримтлах шаардлагатай. Үүний эхний шаардлага нь н функц маш хурдан хялбар байх ёстой. Хоёр дахь шаардлага нь н функцээр хаяглагдах түлхүүрүүд хамгийн бага зөрчилтэйгээр хүснэгтийн м байрлалд байрласан байх шаардлагатай. Гэвч бодит байдал дээр түлхүүрүүд болон хаягуудыг урьдчилан мэдэхгүй тохиолдолд хоёр дахь шаардлагыг төгс хангаж чаддаггүй. Үйлдлүүд : • Get(theKey) • Put(theKey, the Element) • Remove(theKey) Зарим нэг түгээмэл ашиглагдах Хэш функцийг авч үзье. Үүнд : • Хуваах арга. Түлхүүрийн тоо n-ээс их м тоог сонгоно. Хаяглалтын зөрчлийг багасгахын тулд м нь анхны тоо байх шаардлагатай. Эндээс n функцийг • Н (к)= k (mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгсөн бол н функцэд шууд ашиглана.Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай . • Нугалах арга . к түлхүүрийг k1 ,k2,k3,……………, kr гэсэн хэсгүүдэд хуваана. Хэсэг (сүүлчийнхээс бусад ) бүрийн оронгийн тоо нь хаягт шаардагдах оронгийн тоотой ижил байна. Үүний дараа хэсгүүдийг хооронд нь нэмэх ба орон хэтэрвэл түүнийг орхино. Н функц нь • Н(k)= k1+k2+k3+………………+kr гэж тодорхойлогддог. Зарим тохиолдолд тэгш индекстэй хэсгийн цицрүүдийг урвуугаар байрлуулан нэмдэг. Квадрат зэрэг дэвшүүлэх арга . Энэ арга нь түлхүүрийг квадрат зэрэг дэвшүүлж гарсан утгын хоёр талын цифрүүдийг устган гол оронгуудаар хаягыг тодорхойлдог. Ялган авах оронгуудын байрлал нь бүх түлхүүрийн ижил байх хэрэгтэй . Жишээлбэл нугалан авах аргаар авч үзсэн жишээ түлхүүрүүдийн хувьд K 3205 7148 2345 k*k 10272025 51093904 5499025 H(k) 72 93 9

 гэж хэш хүснэгтийн хаягийг  тодорхойлно.

Салангид гинжин арга.Гинжин арга нь энгийн дараалан хайх аргаар хийгдэх харьцуулалтаартоог коэффициентээр багасдаг . Хаягийн зөрчлийг зохицуулах дараачийн аргыг нээлттэй хаяглалтын арга гэдэг. Хэрэв к түлхүүртэй өгөгдлийг H(k)=h функцээр хаягийг нь тодорхойлсон хүснэгт оруулах (Мөн хүснэгтээс хайх) үед h(хаяг) байрлал аль хэдийн өөр өгөгдөлд эзлэгдсэн байвал h байрлалаас хойш тааралдах хамгийн эхэнд тааралдах сул байрлалд оруулдаг. Нээлттэй хаяглалтын хамгийн энгийн аргыг шугаман тандах арга гэнэ. Энэ арга нь хүснэгтийн хаягийн зөрчил гарсан байрлалын түлхүүртэй харьцуулан танддаг. Өөрөөр хэлбэл хайлтыг хүснэгтийн h, h+1, h+2 ……. байрлалуудаас шугаман хайлтыг гүйцэтгэдэг. Энэ үед дараах гурван тохиолдол гарах болно. Хэрэв дараачийн байрлал дахь түлхүүртэй адил бол хайлт амжилттай болно . Хэрэв дараачийн байрлал нь бол хайлт амжилтгүй болно.Хэрэв дээрх хоёр нөхцлийн аль нь биелэхгүй (хайж буй түлхүүрээс өөр түлхүүр дараачийн байрлалд байвал ) бол тандалтыг дараачийн элементүүдэд джс дараалан хийхдээ хоосон байрлал гартал эсвэл хайж буй элемент олдтол гүйцэтгэдэг. Хэрэв хайж буй түлхүүртэй өгөдлийг хүснэгтэд оруулах бол хайлт амжилтгүй болсон чөлөөтэй байрлалд оруулна. Жишээ код: import java.util.*;

public class HashTable {

  protected static class HashEntry
  {
     protected Object key;
     protected Object element;
     private HashEntry() {}
    
     private HashEntry(Object theKey, Object theElement)
     {
        key = theKey;
        element = theElement;
     }
  }
  protected int divisor;         
  protected HashEntry [] table;  
  protected int size;       
  public HashTable(int theDivisor)
  {
     divisor = theDivisor;
  
 
     table = new HashEntry [divisor];
   public Object get(Object theKey)
  {
     int b = search(theKey);
     if (table[b] == null || !table[b].key.equals(theKey))
        return null;           
     return table[b].element; 
  }
  public Object put(Object theKey, Object theElement)
  {
     int b = search(theKey);
     if (table[b] == null)
     {
        table[b] = new HashEntry(theKey, theElement);
        size++;
        return null;
     }
     else
     {
        if (table[b].key.equals(theKey))
        {
           Object elementToReturn = table[b].element;
           table[b].element = theElement;
           return elementToReturn;
        }
        else 
           throw new IllegalArgumentException("table is full");
     }
  }
  public void output()
  {
     for (int i = 0; i < divisor; i++)
        if (table[i] == null)
           System.out.println("null");
        else
           System.out.println(table[i].element);
  }
  public static void main (String [] args)
  {
     HashTable h = new HashTable(11);
     h.put(new Integer(80), new Integer(80));
     h.put(new Integer(40), new Integer(40));
     h.put(new Integer(65), new Integer(65));
     h.output();
     System.out.println();
     h.put(new Integer(58), new Integer(58));
     h.put(new Integer(24), new Integer(24));
     h.output();
     System.out.println();
     h.put(new Integer(2), new Integer(2));
     h.put(new Integer(13), new Integer(13));
     h.put(new Integer(46), new Integer(46));
     h.output();
     System.out.println();
     try {h.put(new Integer(99), new Integer(99));}
     catch (Exception e)
     {System.out.println(" No memory for 99");}
     System.out.println();
 
     h.put(new Integer(7), new Integer(29));
     h.output();
  }

}

Start a discussion with Sw12d012

Talk pages are where people discuss how to make content on Википедиа the best that it can be. Start a new discussion to connect and collaborate with Sw12d012. What you say here will be public for others to see.

Start a discussion