Using HashMap to improve search performance in Java

straight left 2021-02-23 16:03:00
using hashmap improve search performance


Java in ,HashMap, It's actually a key value pair . One Key, Corresponds to a value ; When writing data , Appoint Key Write the corresponding value ; Read by Key Find the corresponding value . It feels like Redis almost .

// establish HashMap object Sites
HashMap<Integer, String> Sites = new HashMap<Integer, String>();
// Add key value pair 
Sites.put(1, "Google");
Sites.put(2, "Runoob");
Sites.put(3, "Taobao");
Sites.put(4, "Zhihu");
// Read 
String val = Sites.get(1);// obtain Google

Why can I use HashMap To improve performance ? The reason is not that HashMap This kind of data structure has better storage performance than others , For example, array , How much more advanced . My main focus is , It's about knowing Key Under the circumstances , It's very fast to find the corresponding value . If you use arrays , The simplest , Use the cycle ; Be careful , Arrange order well , Search in half ( Two points search ). It's not as good as Key stay HashMap Read directly from . do not know why HashMap Why is the search so fast , It's probably the storage structure , What tree was used , And for Key It's indexed . This is another subject , I'll learn about it later . yesterday , I just took advantage of this feature , Will run for several hours without the end of the problem , It only took a dozen seconds .

Questions as follows :
Yes 25 Ten thousand records , Each record contains latitude and longitude ; There are different records with the same coordinates . Now I want to put records with the same coordinates together .

If the data is stored in a database , Then use SQL Coordinate grouping , It should solve the problem . However, there is no database , Data is from gdb It's read from the file .

ok , Save the data in an array , Create a new set ; Then loop the array , Compare one by one with the records in the new set , If the coordinates are the same, merge them into a new set , If not, insert a new set . It's the easiest . result 2 An hour passed , There's no sign of an end yet .

Think about it , The new set is getting bigger and bigger , There are more and more comparisons , It's like rice on a chessboard , There is twice as much rice in each grid as in the previous one ; In the end, even the whole country's grain depots are filled with rice , I can't fill the whole chessboard .

take 25 Ten thousand records should be sorted before processing ? Sorting alone is too busy , No way .

take 25 Ten thousand records are saved in the database first , Another group ? It should work , But I always feel stupid , And the speed should also be in minutes .

Finally decided to use HashMap To make this new collection .
As mentioned above ,HashMap according to Key To write or read values . The point is this Key How can I get . The above example , It's the person who wrote the code who gave some characters as Key. And in our project , You can use the hash value of the sum of longitude and latitude as Key. With the same hash value , It's the same latitude and longitude , You just need to determine what's in the new set , Is there this Key The corresponding element is OK , There's no need to compare at all .

Because there are two different longitudes and latitudes together , The result is the same possibility , So let's start with longitude multiply 1000, Plus latitude , In this way, we can basically eliminate the chance of conflict .

The code is as follows :

private HashMap<Long,SimpleItem> recGeo(HashMap<Long, SimpleItem> map,String geo,int j){

/*
Combine records of the same coordinates into one
HashMap<Long, SimpleItem> map, New collection
String geo, Coordinate string
int j Record ID
*/
try {

Point p = (Point)reader.read(geo);
/*
Calculate the hash value
Because if you use loops to compare , Too much data , It's too slow
To avoid longitude in different coordinates + In the case of the same latitude result , Change longitude * 1000 Add it up
*/
// Calculation Key
long k = Long.valueOf(Double.doubleToLongBits(p.getX() * 1000 + p.getY())).hashCode();
SimpleItem si = map.get(k);
if(si != null){
// In the new set Key The corresponding element already exists , It should be a record of the same coordinates 
si.getPointers().add(j);// Merger 
} else {
// Otherwise insert 
si = new SimpleItem();
si.setGeo(geo);
List<Integer> pointers = new ArrayList();
pointers.add(j);
si.setPointers(pointers);
map.put(k,si);
}
} catch (ParseException e) {

e.printStackTrace();
}
return map;
}
private static GeometryFactory geometryFactory = JTSFactoryFinder.getGeometryFactory( null );
private static WKTReader reader = new WKTReader( geometryFactory );
class SimpleItem{

private Point geo;
private List<Integer> pointers;
public Point getGeo() {

return geo;
}
public void setGeo(String geo) {

try {

this.geo = (Point)reader.read(geo);
} catch (ParseException e) {

e.printStackTrace();
}
}
public List<Integer> getPointers() {

return pointers;
}
public void setPointers(List<Integer> pointers) {

this.pointers = pointers;
}
}

In a few seconds , The new set gives 5 Ten thousand elements .

版权声明
本文为[straight left]所创,转载请带上原文链接,感谢
https://javamana.com/2021/02/20210223155924192w.html

  1. Spring can still play like this! Ali's new spring product has successfully overturned my understanding of spring!
  2. IntelliJ idea can also draw mind maps. It's really the strongest ide!
  3. JavaScript performance optimization [inline cache] V8 engine features
  4. linux 配置java环境
  5. linux find 查找文件
  6. 深入理解 Web 协议 (三):HTTP 2
  7. IntelliJ IDEA 相关问题记录
  8. Deep understanding of Web protocol (3): http 2
  9. 深入理解 Web 协议 (三):HTTP 2
  10. 腾讯IEG开源AI SDK:自动化测试吃鸡、MOBA类游戏
  11. Mysql Command
  12. Configuring Java environment with Linux
  13. Find files in Linux
  14. docker-Dockerfile 创建镜像
  15. Redis Cluster
  16. 深入理解 Web 协议 (三):HTTP 2
  17. JavaScriptBOM操作
  18. JavaScriptBOM操作
  19. Deep understanding of Web protocol (3): http 2
  20. Record of IntelliJ idea related problems
  21. Deep understanding of Web protocol (3): http 2
  22. Tencent IEG open source AI SDK: automatic testing of chicken eating and MoBa games
  23. Mysql Command
  24. Docker dockerfile create image
  25. Redis Cluster
  26. 死磕Spring之IoC篇 - 文章导读
  27. Deep understanding of Web protocol (3): http 2
  28. JavaScript BOM operation
  29. JavaScript BOM operation
  30. 死磕Spring之IoC篇 - 文章导读
  31. k8s node 操作与维护
  32. k8s 证书更新
  33. 【Java面试题第三期】JVM中哪些地方会出现内存溢出?出现的原因是什么?
  34. HashMap连环问你能答出几道?
  35. k8s-cronjob
  36. k8s-cert
  37. 头条面试官:说说Kafka的消费者提交方式,怎么实现的
  38. 什么是HTTPS以及如何实施HTTPS?
  39. Spring: an introduction to IOC
  40. Spring: an introduction to IOC
  41. Operation and maintenance of k8s node
  42. K8s certificate update
  43. vue使用sdk进行七牛上传
  44. k8s-dns
  45. JavaScript 邮箱验证 - 正则验证
  46. k8s-dashboard
  47. HashMap连环问你能答出几道?
  48. Where does memory overflow occur in the JVM? What are the reasons for this?
  49. How many questions can you answer?
  50. k8s-cronjob
  51. spring注解--Transactional
  52. k8s-cert
  53. Will the Spring Festival holiday be extended to February 27 in 2021? Here comes the response
  54. Headline Interviewer: talk about Kafka's consumer submission method, how to achieve it
  55. 【k8s集群】搭建步骤
  56. k8s-kubeadm
  57. k8s-etcd
  58. What is HTTPS and how to implement it?
  59. Java中使用HashMap改进查找性能
  60. maven发布jar包运行时找不到类问题