java - searching the perfect data structure for storing and retrieving the elements -
this question exact duplicate of:
i have choose 1 data structure need below explaining conditions there following values
abc,def,rty,ytr,dft map row r1b1 (actully key combination of r1+b1) abeerc,dfffef,rggty map row r1b2 (actully key combination of r1+b2) key value abc,def,rty,ytr,dft ---> r1b1 abeerc,dfffef,rggty ---> r1b2 now, example, let's say, if ytr able retrieve r1b1 or, let's say, value rggty able retrieve r1b2
now case matters of search, complexity , time taken things have go in sequence
for example, first pick first line search ytr, first match abc not match have match def not again match match rty not match match ytr , find key r1b1 finally
similarly if second string need searched lets rggty scan first row in not find value search continue second row , in second row in third element rggty element retrieve r1b2 value
let's say, if put thing in map sequence search go on key , able find corresponding value
folks please advise best data structure can implement in java in have search keys items find corresponding value in fast time not hit performance ,the kind of data structure performance should high
please advise folks great if 1 can advise me show how can achieved using digital trees
as comments suggest can use hashmap or hashtable,
if insist on implementing structure on own suggest search trie.
in search trie number of maximum comparisons required retrieve data equal length of key used, retrieve data given keys(abc,def,rty,ytr,dft) 3 comparisons required
consider following wikipedia link: https://en.wikipedia.org/wiki/trie
below quick , dirty implementation of search trie (provided keys standard ascii letters) :)-
public class dictionarynode { dictionarynode next[]; string data; dictionarynode() { next=new dictionarynode[128]; for(int i=0;i<next.length;i++) { next[i]=null; } data=null; } } public class dictionary { dictionarynode root; dictionary() { root = new dictionarynode(); } public boolean add(string key,string data) { char[]ch=key.tochararray(); dictionarynode current=root; for(int i=0;i<ch.length;i++) { if(current.next[ch[0]]==null) { current.next[ch[0]]=new dictionarynode(); } current=current.next[ch[0]]; } if(current.data==null) { current.data=data; return true; } else { return false; } } public string search(string key) { char[]ch=key.tochararray(); dictionarynode current=root; for(int i=0;i<ch.length;i++) { if(current.next[ch[0]]==null) { return null; } else { current=current.next[ch[0]]; } } return current.data; } } public class main { public static void main(string []args) { dictionary d=new dictionary(); d.add("abc", "r1b1"); d.add("def", "r1b1"); d.add("rty", "r1b1"); d.add("ytr", "r1b1"); d.add("dft", "r1b1"); system.out.println(d.search("abc")); system.out.println(d.search("ab")); } }
Comments
Post a Comment